GeeksforGeeks: Maximum Weight Transformation of String
Problem Overview
You are given a string s containing only the characters 'A' and 'B'. You can toggle any character (changing 'A' to 'B' or 'B' to 'A').
The weight of the string is calculated based on these rules:
An alternating adjacent pair ("AB" or "BA") adds 4 to the weight. Each character can belong to at most one pair.
Any character that doesn't belong to a pair adds 1 to the weight.
Every toggle you perform reduces the total weight by 1.
Your objective is to find the maximum possible weight you can achieve by optimally forming pairs and toggling characters.
Example: s = "ABB" The original string already has an alternating pair "AB" which gives a weight of 4, and the remaining 'B' gives a weight of 1. No toggles are needed. The maximum weight is 4 + 1 = 5.
View the Problem on GeeksforGeeks | Watch the Video Tutorial
The Approach: Dynamic Programming with Memoization
Since we have multiple choices at each character (either leave it alone or pair it with the next character by potentially toggling), this problem exhibits overlapping subproblems and optimal substructure. This makes it a perfect candidate for Dynamic Programming (DP).
At any index i, we have two main choices:
Don't pair the current character: We take a weight of 1 for the single character and move to
i + 1.Pair the current character with the next one:
If
s[i]ands[i+1]are already different, they form a valid pair naturally. We add a weight of 4 and move toi + 2.If
s[i]ands[i+1]are the same, we need exactly one toggle to make them alternating. The pair gives a weight of 4, but the toggle costs 1, resulting in a net weight gain of 3. We then move toi + 2.
We memoize the results using a dp array to avoid recalculating the maximum weight for the same index.
Step-by-Step Code Logic
Initialize DP Array: Create a
vector<int> dpof the same size as the string, initialized with -1 to keep track of computed states.Base Cases in Recursion:
If the index
igoes beyond the string length, return 0.If
iis at the very last character (i == s.size() - 1), it can't be paired, so it contributes a weight of 1.
Check Memoization: If
dp[i]is not -1, return the already computed value for this index to save time.Calculate Single Character Weight: Calculate the result if we don't pair
s[i]. Setres = 1 + recursive(i + 1).Calculate Pair Weight: Check the adjacent character
s[i+1]:
If
s[i] != s[i+1], updateresto the maximum of its current value and4 + recursive(i + 2).If
s[i] == s[i+1], updateresto the maximum of its current value and3 + recursive(i + 2).
Store and Return: Save the maximum result in
dp[i]and return it.
C++ Code Implementation
class Solution {
public:
int recursive(int i, string &s, vector<int> &dp) {
if (i >= s.size()) return 0;
if (i == s.size() - 1) return 1;
if (dp[i] != -1) return dp[i];
int res = 1 + recursive(i + 1, s, dp);
if (s[i + 1] != s[i]) {
res = max(res, 4 + recursive(i + 2, s, dp));
} else {
res = max(res, 3 + recursive(i + 2, s, dp));
}
return dp[i] = res;
}
int getMaxWeight(string &s) {
vector<int> dp(s.size(), -1);
return recursive(0, s, dp);
}
};Complexity Analysis
Time Complexity: O(N), where N is the length of the string. Thanks to the memoization array, we evaluate each index at most once.
Space Complexity: O(N) for the recursion stack and the dp array used to store the intermediate results.