Solution: Maximum Score From Removing Substrings (ver. 1)

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

---

Note: This is my first version of a solution post for this problem. Though the concept is cool, the much better/easier solution is posted here.

---

Leetcode Problem #1717 (Medium): 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". 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 <= 10^5
• 1 <= x, y <= 10^4
• s consists of lowercase English letters.

---

Idea:

The problem here is twofold. The first issue is relatively easy in that we should greedily perform the higher-valued operation as many times as possible before doing the lower-valued operation. We could continuously splice the input as the operations suggest, but that would be grossly inefficient, so instead we can just use a few pointers to avoid having to actually do the splicing.

But the second issue is that we have to run through S multiple times, which means a simple two-pointer system won't work by itself without the means to "remember" the pointer shifts between the first and second pass.

This means that we'll have to have some way of storing the string as it's modified after the first set of operations before we begin the second. We could always create a new stack array into which we could push the values from S, but at this point, it's more efficient to split S into an array, which will allow us to rewrite individual values of S in place.

Once we do that, we can run a two-pointer system: one pointer (j) will keep track of the current position in S, then we can treat the first portion of S as if it were a stack and use the other pointer (i) to keep track of the "end" of that stack.

      S = "abxaabb" = [ "a", "b", "x", "a", "a", "b", "b" ]
pattern = "ab"


                i,j                        // Start i & j at the pattern length
S = [ "a", "b", "x", "a", "a", "b", "b" ]  // Then check the last 2 "stack" entries
       ^*!!*^                              // to see if they match the pattern

       i <-- <-- j                         // If they match, then we move i back 2
S = [ ___, ___, "x", "a", "a", "b", "b" ]  // simulating removal from the "stack"
                                           // Those values will be overwritten later

       i         j                         // At the end of each iteration
S = [ "x", ___, "x", "a", "a", "b", "b" ]  // we shift the next value to the "stack"
       ^----------                         // by overwriting S[i] with S[j]...

        --> i     --> j                    // ...and then we increase the 2 pointers
S = [ "x", ___, ___, "a", "a", "b", "b" ]  // for the start of the next iteration


             --> i     --> j               // No match is found
S = [ "x", "a", ___, ___, "a", "b", "b" ]  // so we just move ahead
            ^----------

                  --> i     --> j          // No match is found
S = [ "x", "a", "a", ___, ___, "b", "b" ]  // so we just move ahead
                 ^----------

                       --> i     --> j
S = [ "x", "a", "a", "b", ___, ___, "b" ]  // A match is found...
                 ^*!*^ ^--------

                 i <-- <--           j
S = [ "x", "a", ___, ___, ___, ___, "b" ]  // ...so we move i back 2


                  --> i               --> j   // Clearly, we must allow j to go one
S = [ "x", "a", "b", ___, ___, ___, ___ ]     // past the end of S to allow for the
            ^*!*^ ^-------------------        // last value of S to complete a match

             --> i <--                    --> j   // Once we're done with this pass
S = [ "x", ___, ___, ___, ___, ___, ___ ]         // anything from i-1 on is garbage
            ^-----------------------------        // and should be removed


S = [ "x" ]                                       // Splice to prepare for pass #2

---

Implementation:

To make the pattern more easy to compare, we can separate out "a" and "b" into separate variables. Then, since we don't know which pattern is more valuable, we can just take advantage of a destructuring assignment to swap out the pattern (a, b) and value variables (X, Y) if necessary before starting.

Then we can just iterate through the two passes. In between the two passes, we will need to splice away the unwanted end of S as well as use the destructuring assignment to swap the pattern and value variables for the second pass.

Then we return the optimal ans.

---

Javascript Code:

var maximumGain = function(S, X, Y) {
    S = S.split('')
    let len = S.length, ans = 0, a = "a", b = "b", i, j
    if (Y > X) [a,b,X,Y] = [b,a,Y,X]
    for (let t = 0; t < 2; t++) {
        for (i = j = 2; j <= len; S[i++] = S[j++])
            if (i > 1 && S[i-2] === a && S[i-1] === b)
                ans += X, i -= 2
        len = i - 1, S.splice(len), [a,b,X,Y] = [b,a,Y,X]
    }
    return ans
};