Maximum Weight Transformation of String

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:

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:

• dp[i - 1]

• dp[i - 2]

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:

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.