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.

Examples

Example 1:

1
2
3
4
5
6
7
8

Input: s = "cdbcbbaaabab", x = 4, y = 5
Output: 19
Explanation:
- Remove the "ba" bracketed in "cdbcbbaaa[ba]b". Now, s = "cdbcbbaaab" and 5 points are added to the score.
- Remove the "ab" bracketed in "cdbcbbaa[ab]". Now, s = "cdbcbbaa" and 4 points are added to the score.
- Remove the "ba" bracketed in "cdbcb[ba]a". Now, s = "cdbcba" and 5 points are added to the score.
- Remove the "ba" bracketed in "cdbc[ba]". Now, s = "cdbc" and 5 points are added to the score.
Total score = 5 + 4 + 5 + 5 = 19.

Example 2:

1
2

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

Solution

Method 1 - Using StringBuilder as Stack

Here’s one way to achieve this:

  1. Decide the order of removal based on the point values x and y. Always start with the operation that gives the higher points.
  2. Use a stack to process the string and remove substrings when detected.
  3. After processing once for one substring, process the resulting string for the other substring.
    • Uses a stack-like mechanism with StringBuilder to process and remove substrings.
    • Iterates through the input string, maintaining a running result in the StringBuilder.
    • Checks the end of StringBuilder for the substring to be removed, and if found, removes it and adds points.

Code

 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

class Solution {
    public int maximumGain(String s, int x, int y) {
         if (x > y) {
             return removeSubstrings(s, "ab", x, "ba", y);
         } else {
             return removeSubstrings(s, "ba", y, "ab", x);
         }        
    }
     private int removeSubstrings(String s, String first, int firstPoints, String second, int secondPoints) {
         int totalPoints = 0;
         StringBuilder sb = new StringBuilder();
         
         // Removing the first type of substring
         totalPoints += removeSubstring(s, first, firstPoints, sb);
 
         // Now process the second type on the remaining string
         StringBuilder finalSb = new StringBuilder();
         totalPoints += removeSubstring(sb.toString(), second, secondPoints, finalSb);
 
         return totalPoints;
     }
     private int removeSubstring(String s, String toRemove, int points, StringBuilder resultSb) {
         int totalPoints = 0;
         int n = s.length();
         char[] chars = s.toCharArray();
         int i = 0;
 
         while (i < n) {
             resultSb.append(chars[i]);
             if (resultSb.length() >= 2) {
                 if (resultSb.substring(resultSb.length() - 2).equals(toRemove)) {
                     resultSb.delete(resultSb.length() - 2, resultSb.length());
                     totalPoints += points;
                 }
             }
             i++;
         }
         return totalPoints;
     }     
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)