Solution: Maximum Score From Removing Substrings (ver. 2)
Tags: algorithms, javascript, java, python
Published: 2021-02-14 23:14:27

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/maximum-score-from-removing-substrings/discuss/1065911).*

---

*Note: This is my second version of a solution post for this problem. This one is the better solution, but [the first version used a cool concept](https://dev.to/seanpgallivan/solution-maximum-score-from-removing-substrings-ver-1-39g2).*

---

####[Leetcode Problem #1717 (*Medium*): Maximum Score From Removing Substrings](https://leetcode.com/problems/maximum-score-from-removing-substrings/)

---

***Description:***

*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`.*

---

***Examples:***

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

Example 2:||
|---:|---|
*Input:*|s = "aabbaaxybbaabb", x = 5, y = 4
*Output:*|20

---

***Constraints:***
 - `1 <= s.length <= 10^5`
 - `1 <= x, y <= 10^4`
 - `s` consists of lowercase English letters.

---

***Idea:***

*Note: This is my second solution post for this problem. I still consider [**the other solution**](https://leetcode.com/problems/maximum-score-from-removing-substrings/discuss/1031736) to be a cool approach, but this one is definitely more efficient and easier to follow.*

One of the easy things to realize about this problem is that we can break the string up into chunks; Only contiguous sets of **"a"** and **"b"** will be meaningful, and any time we see a character other than those two, we effectively end one segment and wait to begin another.

The other thing we can realize fairly easily is that we should **greedily** prioritize whichever pattern is worth more. To make things easier, we can prefix our main code with some variable swaps depending on which pattern has a higher value. For the remainder of this post, we can just assume that **"ab" > "ba"** and therefore **a = "a"** and **b = "b"**.

If we consider a segment of mixed **"a"**'s and **"b"**'s, we should have little problem going through it and accounting for all matches to the better pattern. We'll just need to keep track of how many **a**'s are immeditely behind our current progress in order to match up with later **b**'s.

But how do we deal with matching the **Y** pattern after matching the **X** pattern as much as possible? To answer that, we have to think about what such a modified string would look like:
```js
segment = "bbaababbaa"                       // initial segment
segment = "bbaa"                             // after pulling out all "ab" patterns

segment = "bbbbabababaaabababaaaabababaaa"   // initial segment
segment = "bbbbaaaaaaaa"                     // after pulling out all "ab" patterns
```
You can see that after matching all possible **"ab"** patterns, we will *always* be left with a similar looking remaining segment: a number of **b**'s followed by a number of **a**'s. From here, we can obviously make as many **"ba"** matches as there are of the smallest number between the counts of **a** and **b**.

Then we just need to remember to clear the store once we reach the end of each segment.

---

***Implementation:***

Unlike the other languages, Java has no convenient way to swap variable contents.

We should either run the iteration one past the end of **S**, or else add the final **Y** matches to our **return** value just in case the last segment goes up to the end of **S**.

---

***Javascript Code:***
```javascript
var maximumGain = function(S, X, Y) {
    let len = S.length, ans = 0, a = "a", b = "b"
    if (Y > X) [a,b,X,Y] = [b,a,Y,X]
    let aStore = 0, bStore = 0
    for (let i = 0, c = S[i]; i <= len; c = S[++i])
        if (c === a) aStore++
        else if (c === b)
            if (aStore) ans += X, aStore--
            else bStore++
        else ans += Y * Math.min(aStore, bStore), aStore = bStore = 0
    return ans
};
```

---

***Python Code:***
```python
class Solution:
    def maximumGain(self, S: str, X: int, Y: int) -> int:
        a,b, ans, aStore,bStore = "a","b", 0, 0,0
        if Y > X: a,b,X,Y = b,a,Y,X
        for c in S:
            if c == a: aStore += 1
            elif c == b:
                if aStore:
                    ans += X
                    aStore -= 1
                else: bStore += 1
            else:
                ans += Y * min(aStore, bStore)
                aStore,bStore = 0,0
        return ans + Y * min(aStore, bStore)
```

---

***Java Code:***
```java
class Solution {
    public int maximumGain(String S, int X, int Y) {
        char a = 'a', b = 'b';
        int ans = 0, aStore = 0, bStore = 0;
        if (Y > X) {
            char ctemp = a;
            a = b;
            b = ctemp;
            int itemp = X;
            X = Y;
            Y = itemp;
        }
        for (char c: S.toCharArray())
            if (c == a) aStore++;
            else if (c == b)
                if (aStore > 0) {
                    ans += X;
                    aStore--;
                } else bStore++;
            else {
                ans += Y * Math.min(aStore, bStore);
                aStore = bStore = 0;
            }
        return ans + Y * Math.min(aStore, bStore);
    }
}
```

---

***C++ Code:***
```c++
class Solution {
public:
    int maximumGain(string S, int X, int Y) {
        char a = 'a', b = 'b';
        int ans = 0, aStore = 0, bStore = 0;
        if (Y > X) swap(a,b), swap(X,Y);
        for (char c: S)
            if (c == a) aStore++;
            else if (c == b)
                if (aStore > 0) ans += X, aStore--;
                else bStore++;
            else ans += Y * min(aStore, bStore), aStore = bStore = 0;
        return ans + Y * min(aStore, bStore);
    }
};
```