1717. Maximum Score From Removing Substrings

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.

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 <= 105
• 1 <= x, y <= 104
• s consists of lowercase English letters.

Approach 01:

class Solution {
public:
    int maximumGain(string s, int x, int y) {
        return x > y ? calculateGain(s, "ab", x, "ba", y) : calculateGain(s, "ba", y, "ab", x);
    }

private:
    int calculateGain(const string& s, const string& firstPair, int firstPoints, const string& secondPair, int secondPoints) {
        int totalPoints = 0;
        vector<char> firstStack;
        vector<char> secondStack;

        for (const char c : s) {
            if (!firstStack.empty() && firstStack.back() == firstPair[0] && c == firstPair[1]) {
                firstStack.pop_back();
                totalPoints += firstPoints;
            } else {
                firstStack.push_back(c);
            }
        }

        for (const char c : firstStack) {
            if (!secondStack.empty() && secondStack.back() == secondPair[0] && c == secondPair[1]) {
                secondStack.pop_back();
                totalPoints += secondPoints;
            } else {
                secondStack.push_back(c);
            }
        }

        return totalPoints;
    }
};

class Solution:
    def maximumGain(self, s: str, x: int, y: int) -> int:
        if x > y:
            return self.calculate_gain(s, "ab", x, "ba", y)
        else:
            return self.calculate_gain(s, "ba", y, "ab", x)

    def calculate_gain(self, s: str, first_pair: str, first_points: int, second_pair: str, second_points: int) -> int:
        total_points = 0
        first_stack = []
        second_stack = []

        for c in s:
            if first_stack and first_stack[-1] == first_pair[0] and c == first_pair[1]:
                first_stack.pop()
                total_points += first_points
            else:
                first_stack.append(c)

        for c in first_stack:
            if second_stack and second_stack[-1] == second_pair[0] and c == second_pair[1]:
                second_stack.pop()
                total_points += second_points
            else:
                second_stack.append(c)

        return total_points

Time Complexity

• String Traversal:

  The function maximumGain involves traversing the input string twice, once for each pair of substrings to calculate the points. Each traversal is \( O(n) \), where \( n \) is the length of the string.

• Overall Time Complexity:

  The overall time complexity is \( O(n) \) since the operations inside each traversal are \( O(1) \) and the string is traversed a constant number of times.

Space Complexity

• Auxiliary Space:

  Two stacks are used to store characters during the traversal of the string. In the worst case, if no pairs are found, both stacks will store all characters of the string.

• Overall Space Complexity:

  The overall space complexity is \( O(n) \) for the two stacks used to store the characters, where \( n \) is the length of the string.