Problem Statement
Given a string s containing only the characters A and B, we can toggle any character.
A toggle changes a character as follows:
A → B
B → A
The weight of the transformed string is calculated using these rules:
An alternating pair, "AB" or "BA", contributes 4.
A character that does not belong to any pair contributes 1.
Each character can belong to at most one pair.
Every toggle decreases the final weight by 1.
The task is to find the maximum possible weight after performing any number of toggles.
Example
Input:
s = "AA"
Output:
3
We can toggle one A to transform the string:
AA → AB
The resulting pair contributes 4, but the toggle costs 1.
Therefore:
Pair weight = 4
Toggle cost = 1
Final weight = 4 - 1 = 3
The maximum possible weight is 3.
Important Observation
The key to solving this problem is understanding what happens when we consider two adjacent characters.
Suppose we want to form a pair using:
s[i - 1] and s[i]
There are two possible cases.
Case 1: The Characters Are Different
For example:
AB
or
BA
These characters already form an alternating pair. No toggle is required.
Therefore:
Pair contribution = 4
Toggle cost = 0
Effective contribution = 4
Case 2: The Characters Are the Same
For example:
AA
or
BB
We can toggle one character to create an alternating pair:
AA → AB
or
BB → AB
The pair contributes 4, but one toggle costs 1.
Therefore:
Effective contribution = 4 - 1
= 3
We can summarize both cases as follows:
Adjacent Characters | Toggle Required | Effective Contribution |
|---|
AB
| No | 4 |
BA
| No | 4 |
AA
| Yes | 3 |
BB
| Yes | 3 |
This observation simplifies the problem. Every adjacent pair has an effective contribution of either 4 or 3.
Why Dynamic Programming?
The problem includes an important restriction: each character can belong to at most one pair.
Consider the string:
ABA
We can choose the first two characters as a pair:
AB | A
Alternatively, we can choose the last two characters:
A | BA
However, we cannot select both AB and BA as pairs because the middle character would belong to two pairs.
This means we must consider whether the current character remains unpaired or forms a pair with the previous character.
Dynamic programming is suitable because the optimal answer for a prefix of the string can be calculated using the optimal answers for smaller prefixes.
Defining the DP State
Let:
dp[i] = Maximum weight obtainable using the first i characters
For example:
dp[0] = Maximum weight using zero characters
dp[1] = Maximum weight using the first character
dp[2] = Maximum weight using the first two characters
...
dp[n] = Maximum weight using the complete string
A single character cannot form a pair, so its contribution is 1.
Therefore, the base cases are:
dp[0] = 0
dp[1] = 1
The final answer is:
dp[n]
Understanding the DP Transitions
When processing the i-th character, we have two choices.
Choice 1: Leave the Current Character Unpaired
An unpaired character contributes 1.
We can take the best answer for the first i - 1 characters and add 1.
The transition is:
dp[i] = dp[i - 1] + 1
Choice 2: Pair the Last Two Characters
We can form a pair using:
s[i - 2] and s[i - 1]
If the characters are different, the pair contributes 4. If they are the same, one toggle is required, so the effective contribution is 3.
Because both characters are used in the pair, we must use dp[i - 2] for the preceding characters.
The transition becomes:
dp[i] = dp[i - 2] + pairWeight
Finally, we select the better of the two choices:
dp[i] = max(
dp[i - 1] + 1,
dp[i - 2] + pairWeight
)
Here, pairWeight is 4 when the adjacent characters differ and 3 when they are the same.
Java Implementation Using Dynamic Programming
The following implementation uses a DP array to calculate the maximum possible weight.
class Solution {
public int getMaxWeight(String s) {
int n = s.length();
// dp[i] = maximum weight using the first i characters
int[] dp = new int[n + 1];
// Base cases
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
// Option 1: Leave the current character unpaired
dp[i] = dp[i - 1] + 1;
// Option 2: Pair the last two characters
int pairWeight;
if (s.charAt(i - 1) != s.charAt(i - 2)) {
// Different characters: AB or BA
// No toggle is required
pairWeight = 4;
} else {
// Same characters: AA or BB
// One toggle is required
pairWeight = 3;
}
dp[i] = Math.max(
dp[i],
dp[i - 2] + pairWeight
);
}
return dp[n];
}
}
Explaining the Java Code
Step 1: Create the DP Array
int[] dp = new int[n + 1];
The array contains n + 1 elements because we need to represent prefixes ranging from zero characters to all n characters.
For example, if the string length is 4:
dp[0] → Zero characters
dp[1] → First character
dp[2] → First two characters
dp[3] → First three characters
dp[4] → Complete string
Step 2: Initialize the Base Cases
dp[0] = 0;
dp[1] = 1;
An empty string has a weight of 0.
A string containing one character has a weight of 1 because that character cannot form a pair.
This implementation assumes that the input string contains at least one character.
Step 3: Calculate the Pair Weight
if (s.charAt(i - 1) != s.charAt(i - 2)) {
pairWeight = 4;
} else {
pairWeight = 3;
}
The code compares the two adjacent characters.
If they are different, they already form an alternating pair, so the contribution is 4.
If they are the same, one toggle is required, reducing the effective contribution to 3.
Step 4: Consider Leaving the Character Unpaired
dp[i] = dp[i - 1] + 1;
This calculates the maximum weight when the current character remains unpaired.
We take the best result for the previous prefix and add the contribution of one unpaired character.
Step 5: Consider Forming a Pair
dp[i - 2] + pairWeight
This option uses the last two characters as a pair.
We use dp[i - 2] because the two characters in the pair cannot be reused in another pair.
This prevents overlapping pairs.
Step 6: Select the Maximum Weight
dp[i] = Math.max(
dp[i],
dp[i - 2] + pairWeight
);
The algorithm compares the results of leaving the current character unpaired and pairing it with the previous character.
The larger value becomes dp[i].
After processing the complete string, dp[n] contains the maximum possible weight.
Dry Run: Example 1
Consider the input:
s = "AA"
Initialization
The string contains two characters.
Initially:
dp[0] = 0
dp[1] = 1
Now, we process the second character.
The last two characters are:
AA
They are identical, so one toggle is required.
Therefore:
pairWeight = 3
Option 1: Leave the Last Character Unpaired
dp[1] + 1
= 1 + 1
= 2
Option 2: Pair Both Characters
dp[0] + 3
= 0 + 3
= 3
We select the maximum:
dp[2] = max(2, 3)
= 3
The final answer is:
3
The optimal transformation is:
AA → AB
The pair contributes 4, and the toggle costs 1.
Therefore, the final weight is 3.
Dry Run: Example 2
Consider:
s = "ABB"
Initially:
dp[0] = 0
dp[1] = 1
Processing the First Two Characters
The first two characters are:
AB
They are different, so:
pairWeight = 4
Option 1: Leave the second character unpaired
dp[1] + 1
= 1 + 1
= 2
Option 2: Pair the first two characters
dp[0] + 4
= 0 + 4
= 4
Therefore:
dp[2] = max(2, 4)
= 4
Processing the Third Character
The last two characters are:
BB
They are identical, so:
pairWeight = 3
Option 1: Leave the last character unpaired
dp[2] + 1
= 4 + 1
= 5
Option 2: Pair the last two characters
dp[1] + 3
= 1 + 3
= 4
Therefore:
dp[3] = max(5, 4)
= 5
The final answer is:
5
The optimal arrangement is:
AB | B
The alternating pair contributes 4, and the remaining character contributes 1.
The total weight is:
4 + 1 = 5
No toggle is required.
Another Example: String Containing Only A Characters
Consider:
s = "AAAA"
Every adjacent pair contains identical characters.
Therefore, each pair has an effective contribution of:
4 - 1 = 3
We can divide the string into two non-overlapping pairs:
AA | AA
Toggle one character in each pair:
AB | AB
Each pair contributes 3 after accounting for its toggle cost.
Therefore:
Total weight = 3 + 3
= 6
The maximum possible weight is 6.
Why Greedy Is Not Enough
A greedy approach that selects every high-value adjacent pair independently will not work because pairs can overlap.
Consider:
ABA
Both adjacent pairs are already alternating:
AB → 4
BA → 4
However, we cannot select both pairs because the middle character would belong to two pairs.
We must choose one of the following arrangements:
AB | A
The total weight is:
4 + 1 = 5
Alternatively:
A | BA
The total weight is also:
1 + 4 = 5
The DP approach handles this restriction by considering only the best result for the first i - 2 characters when forming a pair from the last two characters.
This ensures that no character belongs to more than one pair.
Complete DP Recurrence
The recurrence relation is:
dp[i] = max(
dp[i - 1] + 1,
dp[i - 2] + pairWeight
)
The pair weight is calculated as follows:
pairWeight = 4, if s[i - 2] != s[i - 1]
pairWeight = 3, if s[i - 2] == s[i - 1]
The base cases are:
dp[0] = 0
dp[1] = 1
The final result is:
dp[n]
Complexity Analysis
Let n represent the length of the input string.
Time Complexity: O(n)
The algorithm processes each character once.
Each iteration performs a constant number of comparisons and arithmetic operations.
Therefore, the time complexity is O(n).
Space Complexity: O(n)
The DP array contains n + 1 elements.
Therefore, the auxiliary space complexity is O(n).
This approach is suitable for strings containing up to 10^5 characters.
Optimizing the Space Complexity
The DP array is useful for understanding the recurrence, but we do not need to store every calculated value.
To calculate dp[i], we only need:
We can replace the array with two variables and maintain the current result during each iteration.
This reduces the auxiliary space complexity from O(n) to O(1).
Space-Optimized Java Solution
class Solution {
public int getMaxWeight(String s) {
int n = s.length();
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
// Represents dp[i - 2]
int prev2 = 0;
// Represents dp[i - 1]
int prev1 = 1;
for (int i = 2; i <= n; i++) {
int pairWeight;
if (s.charAt(i - 1) != s.charAt(i - 2)) {
pairWeight = 4;
} else {
pairWeight = 3;
}
int current = Math.max(
prev1 + 1,
prev2 + pairWeight
);
// Move the DP states forward
prev2 = prev1;
prev1 = current;
}
return prev1;
}
}
Why Does the Optimized Solution Work?
The variable prev2 stores the result for the prefix ending two characters earlier.
The variable prev1 stores the result for the immediately preceding prefix.
During each iteration, the algorithm calculates the current maximum weight using the same recurrence as the original DP solution.
After calculating the result, it updates both variables so they represent the previous two states for the next iteration.
Because the algorithm stores only two previous results, it no longer needs an array.
The complexity is:
Complexity | Value |
|---|
Time | O(n)
|
Auxiliary Space | O(1)
|
Both implementations calculate the same maximum weight. The optimized version simply uses less memory.
Key Takeaways
The main insight is to convert the character-toggling operation into a fixed contribution for each possible pair.
An existing alternating pair, AB or BA, contributes 4 without requiring a toggle.
A pair containing identical characters, AA or BB, contributes 3 after accounting for the cost of one toggle.
An unpaired character contributes 1.
The problem can therefore be viewed as selecting non-overlapping adjacent pairs while maximizing the total weight.
Dynamic programming provides a straightforward solution using the recurrence:
dp[i] = max(
dp[i - 1] + 1,
dp[i - 2] + pairWeight
)
The standard implementation runs in O(n) time and uses O(n) auxiliary space. By retaining only the two previous DP states, we can reduce the auxiliary space complexity to O(1) without changing the time complexity.
Join the conversation! Your thoughts help the community grow.