# 1717. Maximum Score From Removing Substrings     • Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 class Solution { public: int maximumGain(string s, int x, int y) { // The assumption that gain("ab") > gain("ba") while removing "ba" first is // optimal is contradicted. Only "b(ab)a" satisfies the condition of // preventing two "ba" removals, but after removing "ab", we can still // remove one "ba", resulting in a higher gain. Thus, removing "ba" first is // not optimal. return x > y ? gain(s, "ab", x, "ba", y) : gain(s, "ba", y, "ab", x); } private: // Returns the points gained by first removing sub1 ("ab" | "ba") from s with // point1, then removing sub2 ("ab" | "ba") from s with point2. int gain(const string& s, const string& sub1, int point1, const string& sub2, int point2) { int points = 0; vector stack1; vector stack2; // Remove "sub1" from s with point1 gain. for (const char c : s) if (!stack1.empty() && stack1.back() == sub1 && c == sub1) { stack1.pop_back(); points += point1; } else { stack1.push_back(c); } // Remove "sub2" from s with point2 gain. for (const char c : stack1) if (!stack2.empty() && stack2.back() == sub2 && c == sub2) { stack2.pop_back(); points += point2; } else { stack2.push_back(c); } return points; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 class Solution { public int maximumGain(String s, int x, int y) { // The assumption that gain("ab") > gain("ba") while removing "ba" first is // optimal is contradicted. Only "b(ab)a" satisfies the condition of // preventing two "ba" removals, but after removing "ab", we can still // remove one "ba", resulting in a higher gain. Thus, removing "ba" first is // not optimal. return x > y ? gain(s, "ab", x, "ba", y) : gain(s, "ba", y, "ab", x); } // Returns the points gained by first removing sub1 ("ab" | "ba") from s with // point1, then removing sub2 ("ab" | "ba") from s with point2. private int gain(final String s, final String sub1, int point1, final String sub2, int point2) { int points = 0; Stack stack1 = new Stack<>(); Stack stack2 = new Stack<>(); // Remove "sub1" from s with point1 gain. for (final char c : s.toCharArray()) if (!stack1.isEmpty() && stack1.peek() == sub1.charAt(0) && c == sub1.charAt(1)) { stack1.pop(); points += point1; } else { stack1.push(c); } // Remove "sub2" from s with point2 gain. for (final char c : stack1) if (!stack2.isEmpty() && stack2.peek() == sub2.charAt(0) && c == sub2.charAt(1)) { stack2.pop(); points += point2; } else { stack2.push(c); } return points; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 class Solution: def maximumGain(self, s: str, x: int, y: int) -> int: # The assumption that gain('ab') > gain('ba') while removing 'ba' first is # optimal is contradicted. Only 'b(ab)a' satisfies the condition of # preventing two 'ba' removals, but after removing 'ab', we can still # remove one 'ba', resulting in a higher gain. Thus, removing 'ba' first is # not optimal. return self._gain(s, 'ab', x, 'ba', y) if x > y \ else self._gain(s, 'ba', y, 'ab', x) # Returns the points gained by first removing sub1 ('ab' | 'ba') from s with # point1, then removing sub2 ('ab' | 'ba') from s with point2. def _gain(self, s: str, sub1: str, point1: int, sub2: str, point2: int) -> int: points = 0 stack1 = [] stack2 = [] # Remove 'sub1' from s with point1 gain. for c in s: if stack1 and stack1[-1] == sub1 and c == sub1: stack1.pop() points += point1 else: stack1.append(c) # Remove 'sub2' from s with point2 gain. for c in stack1: if stack2 and stack2[-1] == sub2 and c == sub2: stack2.pop() points += point2 else: stack2.append(c) return points