Maximum Score From Removing Substrings
Understanding the Problem
We have a string made of lowercase letters, and we can repeatedly remove either "ab" or "ba" from it, scoring x or y points respectively each time. The goal is to maximize the total score.
Only the characters 'a' and 'b' matter. Any other character acts as a wall that separates independent groups of a's and b's, because a removal needs an 'a' adjacent to a 'b' and a wall character can never sit between two characters that get removed. Within each group, the question is how to pair up a's and b's to score the most.
Ordering decides the score. If removing "ab" pays more than "ba" (x > y), remove all "ab" pairs first, then remove whatever "ba" pairs remain from the leftovers. If y > x, do the opposite. Each 'a' and each 'b' can take part in at most one removal, so spending a character on the higher-scoring pair whenever possible never loses points compared to saving it for the lower-scoring pair.
Key Constraints:
1 <= s.length <= 10^5: a solution that repeatedly scans and rebuilds the string after each removal is O(n^2) and too slow at this length. We want a single-pass O(n) method.1 <= x, y <= 10^4: both values are positive, so every removal we can make adds points. There is never a reason to skip a removal. The maximum possible score is about (10^5 / 2) x 10^4 = 5 x 10^8, which fits in a 32-bit signed integer.sconsists of lowercase English letters: characters other than 'a' and 'b' act as separators and cannot be part of any removal.
Approach 1: Brute Force (Repeated Scanning)
Intuition
Repeatedly scan the string for the higher-value pair and delete it. If x >= y, search for "ab", remove the first one found, add x to the score, and scan again. Once no "ab" remains, switch to "ba" and repeat. If y > x, do the reverse: clear out all "ba" pairs first, then "ab".
This is the by-hand method, and it is correct. The cost is that deleting a pair shifts the rest of the string and forces another scan, so the work grows quickly on long inputs.
Algorithm
- Determine which pair to prioritize: if x >= y, the high-priority pair is "ab" and the low-priority pair is "ba". Otherwise, swap them.
- Convert the string to a mutable list of characters.
- First pass: repeatedly scan for the high-priority pair. When found, remove those two characters and add the corresponding points. Restart the scan.
- Second pass: repeatedly scan for the low-priority pair. Same process.
- Return the total score.
Visualization and Code
Loading animation...
- Time Complexity: O(n^2). In the worst case, each removal triggers a rescan from near the beginning. With up to n/2 removals, each requiring an O(n) scan, the total is O(n^2).
- Space Complexity: O(n). We store the string as a mutable list/StringBuilder of length n.
After each removal, only the characters that become newly adjacent at the deletion point can form a new pair. A stack captures exactly that adjacency: it keeps the running sequence of unremoved characters, with the most recently kept character on top. The next approach uses one to process each character a single time.
Approach 2: Greedy with Stack (Optimal)
Intuition
A stack processes the string in one pass. We push characters one at a time. Before pushing, we compare the current character against the character on top of the stack. If they form the pair being removed, we pop the top instead of pushing and add the points. This removes the pair without rebuilding the string, and it handles cascades correctly: after a pop, the new top is whatever sat behind the removed pair, which is exactly the character that becomes adjacent once the pair is gone.
One stack pass removes every copy of a single pair. To handle both pairs in priority order, run two passes. The first pass removes the higher-value pair across the whole string. Its leftovers feed a second pass that removes the lower-value pair. If x > y the higher-value pair is "ab"; if y > x it is "ba".
Within one segment of a's and b's, the number of removals is capped at min(countA, countB), since every removal consumes one 'a' and one 'b'. The greedy strategy reaches that cap while filling it with the most valuable pairs: it removes as many higher-value pairs as the layout permits, then spends the remaining characters on lower-value pairs. Removing the higher-value pair first never blocks a removal the other order would have allowed, because both orders consume one 'a' and one 'b' per pair and bottom out at the same min(countA, countB) total. No alternative ordering can score more. This is the standard exchange argument.
Algorithm
- Determine priority: if x >= y, the first pair to remove is "ab" (worth x points), and the second is "ba" (worth y points). If y > x, swap them.
- First stack pass: iterate through the string, pushing characters onto a stack. Whenever the stack top and current character form the high-priority pair, pop the stack and add the higher points.
- Collect the remaining characters from the stack (this is what is left after removing all high-priority pairs).
- Second stack pass: iterate through the remaining characters with a fresh stack. Whenever the stack top and current character form the low-priority pair, pop and add the lower points.
- Return the total score.
Visualization and Code
Loading animation...
- Time Complexity: O(n). Each character is pushed onto a stack and popped at most once per pass. With two passes, the total work is O(2n) = O(n).
- Space Complexity: O(n). The stack can hold up to n characters in the worst case (when no pairs are found).
The stack approach uses O(n) space, but the stack only tracks how many characters are waiting within the current segment. The next approach replaces it with two integer counters and drops the space to O(1).
Approach 3: Counting (Optimal, O(1) Space)
Intuition
The stack only ever holds 'a' and 'b' characters waiting inside the current segment, and a separator resets it to empty. That makes its contents simple enough to replace with two integers. While scanning a segment, track count1, the number of c1 characters (the high pair's first character) currently waiting. When c2 (the high pair's second character) arrives, it either consumes one waiting c1, forming a high-value pair, or, if none is waiting, accumulates in count2. A separator or the end of the string closes the segment, and the leftovers form min(count1, count2) low-value pairs.
Incrementing count1 mirrors pushing c1 onto the stack, and decrementing it when c2 arrives mirrors popping to form the high-value pair. Because both pair types within a segment consume one 'a' and one 'b', the high-value pass leaves exactly what a stack would leave: count1 unmatched c1's and count2 unmatched c2's, with no high-value pair possible between them, since every c2 that had a c1 before it already paired. Those leftovers form min(count1, count2) low-value pairs, the cap for the segment. Summing over segments matches the total from two stack passes.
Algorithm
- Determine priority order (same as before).
- Iterate through the string. Track the count of the "first character" of the high-priority pair.
- When we see the "second character" of the high-priority pair and the count > 0, decrement the count and add high points.
- When we see the "second character" but count is 0, increment a separate counter for unpaired second characters.
- Non-'a'/'b' characters reset the segment: resolve remaining low-value pairs as min(count1, count2), then reset both counters.
- After the loop, resolve the final segment the same way.
Visualization and Code
Loading animation...
- Time Complexity: O(n). Single pass through the string, O(1) work per character.
- Space Complexity: O(1). Only a few integer counters. No stack or auxiliary data structure needed.