# Maximum Score From Removing Substrings
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-score-from-removing-substrings)
Canonical: https://scaleengineer.com/dsa/problems/maximum-score-from-removing-substrings
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String, Stack
**Companies:** [Swiggy](https://scaleengineer.com/companies/swiggy)
---
## Problem
You are given a string `s` and two integers `x` and `y`. You can perform two types of operations any number of times.

* Remove substring `"ab"` and gain `x` points.  
  * For example, when removing `"ab"` from `"cabxbae"` it becomes `"cxbae"`.
* Remove substring `"ba"` and gain `y` points.  
  * For example, when removing `"ba"` from `"cabxbae"` it becomes `"cabxe"`.

Return _the maximum points you can gain after applying the above operations on_ `s`.

**Example 1:**

**Input:** s = "cdbcbbaaabab", x = 4, y = 5
**Output:** 19
**Explanation:**
- Remove the "ba" underlined in "cdbcbbaaabab". Now, s = "cdbcbbaaab" and 5 points are added to the score.
- Remove the "ab" underlined in "cdbcbbaaab". Now, s = "cdbcbbaa" and 4 points are added to the score.
- Remove the "ba" underlined in "cdbcbbaa". Now, s = "cdbcba" and 5 points are added to the score.
- Remove the "ba" underlined in "cdbcba". Now, s = "cdbc" and 5 points are added to the score.
Total score = 5 + 4 + 5 + 5 = 19.

**Example 2:**

**Input:** s = "aabbaaxybbaabb", x = 5, y = 4
**Output:** 20

**Constraints:**

* `1 <= s.length <= 105`
* `1 <= x, y <= 104`
* `s` consists of lowercase English letters.

# Approaches
## Brute-Force Simulation
This approach directly simulates the process described in the problem. It repeatedly scans the string to find and remove occurrences of "ab" or "ba", adding the corresponding points to a running total. The choice of which substring to remove at each step is made greedily based on which one offers more points.
**Time:** O(N^2) or worse. In the worst case, we might perform O(N) removals, and each removal involves a string search and modification, which takes O(N) time. · **Space:** O(N), where N is the length of the string. A new string or `StringBuilder` is often created in each step of removal.
**Pros:** Conceptually simple and easy to understand.
**Cons:** Extremely inefficient due to repeated string searching and manipulation.; Each removal operation on a string is costly, typically O(N).; Will result in a 'Time Limit Exceeded' error for the given constraints.
### Explanation
The brute-force method involves iterating through the string in a loop. In each iteration, we search for the substrings "ab" and "ba". Based on the scores `x` and `y`, we decide which one to remove first. For instance, if `x` is greater than `y`, we prioritize finding and removing "ab". After a removal, the string is modified, and the process repeats from the beginning of the new, shorter string. This continues until no more "ab" or "ba" substrings can be found. While simple to conceptualize, this method is very slow because string search and modification operations inside a loop lead to a high time complexity.
### Algorithm
1. Initialize `totalScore = 0`.
2. Start a loop that continues as long as removals are possible.
3. Inside the loop, set a flag `found = false`.
4. Determine which pair to prioritize. If `x > y`, prioritize "ab". Otherwise, prioritize "ba".
5. Search for the high-priority pair (e.g., using `s.indexOf("ab")`).
6. If found, remove it from the string, add its score to `totalScore`, set `found = true`, and continue to the next iteration of the loop.
7. If the high-priority pair is not found, search for the low-priority pair.
8. If the low-priority pair is found, remove it, add its score, set `found = true`, and continue.
9. If neither pair is found (`found` remains `false`), break the loop.
10. Return `totalScore`.

## Greedy Two-Pass Stack Approach
A more efficient approach is to use a greedy strategy. The key observation is that it's always optimal to prioritize removing the substring that yields a higher score. For example, if `x > y`, we should remove as many "ab"s as possible before considering "ba"s. This can be implemented in two passes. The first pass removes all instances of the higher-scoring pair, and the second pass removes all instances of the lower-scoring pair from the resulting string. A stack (or a `StringBuilder` used as a stack) is an effective tool for removing adjacent pairs in linear time.
**Time:** O(N), as we iterate through the string a constant number of times (twice). · **Space:** O(N), where N is the length of the string. This space is used by the `StringBuilder`s to store the intermediate and final strings.
**Pros:** Efficient with a linear time complexity.; Guaranteed to find the optimal solution due to the greedy strategy.; Passes the given constraints.
**Cons:** Requires O(N) extra space to hold the intermediate string and the stack used for processing.
### Explanation
This greedy approach is implemented with two main steps. First, we determine which pair, "ab" or "ba", has a higher score. Let's assume `x >= y`, making "ab" the high-priority pair.

We perform the first pass over the string `s` to remove all "ab"s. We can use a `StringBuilder` as a character stack. We iterate through `s`, and for each character, if it's a 'b' and the last character in our `StringBuilder` is an 'a', we've found an "ab" pair. We remove the 'a' from the `StringBuilder` and add `x` to our total score. Otherwise, we append the current character to the `StringBuilder`.

After the first pass, the `StringBuilder` contains a string with no "ab"s. We then perform a second pass on this new string to remove all "ba"s, adding `y` for each one found, using the same stack-based technique. The sum of scores from both passes gives the maximum possible score.

```java
class Solution {
    public int maximumGain(String s, int x, int y) {
        if (x < y) {
            // Ensure x is always the score for the higher-priority pair
            int temp = x;
            x = y;
            y = temp;
            s = new StringBuilder(s).reverse().toString();
        }

        long totalScore = 0;
        
        // First pass: remove "ab" (higher score)
        StringBuilder sb1 = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (c == 'b' && sb1.length() > 0 && sb1.charAt(sb1.length() - 1) == 'a') {
                sb1.deleteCharAt(sb1.length() - 1);
                totalScore += x;
            } else {
                sb1.append(c);
            }
        }

        // Second pass: remove "ba" (lower score)
        StringBuilder sb2 = new StringBuilder();
        for (char c : sb1.toString().toCharArray()) {
            if (c == 'a' && sb2.length() > 0 && sb2.charAt(sb2.length() - 1) == 'b') {
                sb2.deleteCharAt(sb2.length() - 1);
                totalScore += y;
            } else {
                sb2.append(c);
            }
        }

        return (int) totalScore;
    }
}
```
### Algorithm
1. Compare `x` and `y` to decide the priority. Let's say `x >= y`. The high-priority pair is "ab" with score `x`, and the low-priority is "ba" with score `y`.
2. Define a helper function, `process(s, pair, score)`, that takes a string, a pair to remove (e.g., "ab"), and its score.
3. Inside `process`, use a stack-like approach (e.g., a `StringBuilder`). Iterate through the input string `s`:
    - If the current character and the last character in the `StringBuilder` form the target `pair`, pop the last character and add the `score` to a running total for this pass.
    - Otherwise, append the current character to the `StringBuilder`.
4. The `process` function returns the score gained and the resulting string (from the `StringBuilder`).
5. **First Pass**: Call `process(original_s, high_priority_pair, high_score)`. This will remove all high-priority pairs. Store the returned score and the new intermediate string.
6. **Second Pass**: Call `process(intermediate_string, low_priority_pair, low_score)`. This will remove all low-priority pairs from the result of the first pass.
7. The total maximum score is the sum of the scores from the two passes.

## Greedy One-Pass Constant Space Approach
This approach optimizes the two-pass method by eliminating the need for an intermediate string, thus reducing the space complexity to constant. It still follows the same greedy principle of prioritizing the higher-scoring pair. Instead of building a new string, we use counters to keep track of the available characters ('a's and 'b's) as we iterate through the string in a single pass. This allows us to calculate the score on the fly.
**Time:** O(N), as we iterate through the string only once. · **Space:** O(1), as we only use a few variables to store counters and the score.
**Pros:** Most optimal solution with O(N) time and O(1) space complexity.; Processes the string in a single pass.
**Cons:** The logic can be slightly more complex to reason about compared to the direct simulation of the two-pass stack approach.
### Explanation
We can achieve the same result as the two-pass approach in a single pass with constant extra space. The idea is to simulate the first pass (removing the high-priority pair) using a counter, and then calculate the score from the second pass based on the remaining characters.

Let's assume `x >= y`, so we prioritize removing "ab". We iterate through the string and maintain a count of available 'a's (`countA`). When we encounter a 'b', if `countA > 0`, we can form an "ab" pair. We add `x` to our score and decrement `countA`. If `countA` is 0, this 'b' cannot form an "ab" with a preceding 'a'. We keep track of these 'b's in a separate counter, `countB`.

Any character that is not 'a' or 'b' acts as a separator. When we encounter a separator, or at the very end of the string, the characters we've counted in `countA` and `countB` represent the leftovers from the first pass. These leftovers are effectively ordered with all 'b's before all 'a's (e.g., `bbb...aaa...`), so they can only form `min(countA, countB)` "ba" pairs. We add `min(countA, countB) * y` to the score and reset the counters when a separator is found.

This method avoids storing the intermediate string, making it the most optimal solution.

```java
class Solution {
    public int maximumGain(String s, int x, int y) {
        if (x < y) {
            return maximumGain(new StringBuilder(s).reverse().toString(), y, x);
        }

        long score = 0;
        int countA = 0;
        int countB = 0;

        for (char c : s.toCharArray()) {
            if (c == 'a') {
                countA++;
            } else if (c == 'b') {
                if (countA > 0) {
                    // Form "ab"
                    score += x;
                    countA--;
                } else {
                    // Cannot form "ab", this 'b' might form "ba" later
                    countB++;
                }
            } else {
                // Separator character
                // Process remaining 'a's and 'b's which can only form "ba"
                score += (long) Math.min(countA, countB) * y;
                countA = 0;
                countB = 0;
            }
        }

        // Process any remaining characters at the end of the string
        score += (long) Math.min(countA, countB) * y;

        return (int) score;
    }
}
```
### Algorithm
1. Compare `x` and `y` to determine the high-priority and low-priority pairs. Let's assume `x >= y`, so "ab" is high-priority.
2. Initialize `score = 0`, and two counters, `count1 = 0` (for 'a') and `count2 = 0` (for 'b').
3. Iterate through the string `s` character by character.
4. If the current character is the first character of the high-priority pair (e.g., 'a'), increment `count1`.
5. If the current character is the second character of the high-priority pair (e.g., 'b'):
    - If `count1 > 0`, it means we can form a high-priority pair. Add the high score (`x`) to `score` and decrement `count1`.
    - Otherwise, this character cannot form a high-priority pair. It might form a low-priority pair later. Increment `count2`.
6. If the current character is neither 'a' nor 'b', it acts as a separator. The pending characters counted by `count1` and `count2` can no longer interact with characters that appear after the separator. The pending characters are effectively arranged such that all `count2` characters appear before all `count1` characters. Thus, they can form `min(count1, count2)` low-priority pairs. Add `min(count1, count2) * low_score` to `score` and reset both counters to 0.
7. After the loop finishes, there might be remaining characters counted in `count1` and `count2`. Perform the same calculation as in step 6: add `min(count1, count2) * low_score` to `score`.
8. If `y > x` initially, simply swap the roles of 'a' and 'b' and `x` and `y` in the logic above.

# Solutions
### Java

```java
class Solution {
public
  int maximumGain(String s, int x, int y) {
    if (x < y) {
      return maximumGain(new StringBuilder(s).reverse().toString(), y, x);
    }
    int ans = 0;
    Deque<Character> stk1 = new ArrayDeque<>();
    Deque<Character> stk2 = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
      if (c != 'b') {
        stk1.push(c);
      } else {
        if (!stk1.isEmpty() && stk1.peek() == 'a') {
          stk1.pop();
          ans += x;
        } else {
          stk1.push(c);
        }
      }
    }
    while (!stk1.isEmpty()) {
      char c = stk1.pop();
      if (c != 'b') {
        stk2.push(c);
      } else {
        if (!stk2.isEmpty() && stk2.peek() == 'a') {
          stk2.pop();
          ans += y;
        } else {
          stk2.push(c);
        }
      }
    }
    return ans;
  }
}

```

### JavaScript

```javascript
function maximumGain ( s , x , y ) { let [ a , b ] = [ ' a ' , ' b ' ]; if ( x < y ) { [ x , y ] = [ y , x ]; [ a , b ] = [ b , a ]; } let [ ans , cnt1 , cnt2 ] = [ 0 , 0 , 0 ]; for ( let c of s ) { if ( c === a ) { cnt1 ++ ; } else if ( c === b ) { if ( cnt1 ) { ans += x ; cnt1 -- ; } else { cnt2 ++ ; } } else { ans += Math . min ( cnt1 , cnt2 ) * y ; cnt1 = 0 ; cnt2 = 0 ; } } ans += Math . min ( cnt1 , cnt2 ) * y ; return ans ; }
```

### CPP

```cpp
class Solution {
public:
  int maximumGain(string s, int x, int y) {
    if (x < y) {
      reverse(s.begin(), s.end());
      return maximumGain(s, y, x);
    }
    int ans = 0;
    stack<char> stk1;
    stack<char> stk2;
    for (char c : s) {
      if (c != 'b')
        stk1.push(c);
      else {
        if (!stk1.empty() && stk1.top() == 'a') {
          stk1.pop();
          ans += x;
        } else
          stk1.push(c);
      }
    }
    while (!stk1.empty()) {
      char c = stk1.top();
      stk1.pop();
      if (c != 'b')
        stk2.push(c);
      else {
        if (!stk2.empty() && stk2.top() == 'a') {
          stk2.pop();
          ans += y;
        } else
          stk2.push(c);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maximumGain(self, s: str, x: int, y: int) -> int: if x < y: return self . maximumGain(s[:: - 1], y, x) ans = 0 stk1, stk2 = [], [] for c in s: if c != 'b': stk1 . append(c) else: if stk1 and stk1[- 1] == 'a': stk1 . pop() ans += x else: stk1 . append(c) while stk1: c = stk1 . pop() if c != 'b': stk2 . append(c) else: if stk2 and stk2[- 1] == 'a': stk2 . pop() ans += y else: stk2 . append(c) return ans

```