Skip to content

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<char> stack1;
    vector<char> stack2;

    // Remove "sub1" from s with point1 gain.
    for (const char c : s)
      if (!stack1.empty() && stack1.back() == sub1[0] && c == sub1[1]) {
        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[0] && c == sub2[1]) {
        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<Character> stack1 = new Stack<>();
    Stack<Character> 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[0] and c == sub1[1]:
        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[0] and c == sub2[1]:
        stack2.pop()
        points += point2
      else:
        stack2.append(c)

    return points