Maximum Score From Removing Substrings

main.md

Question

Approach

I decided to always prioritize removing the more valuable pattern first—either "ab" or "ba"—depending on which of x or y is greater. I wrote a helper function remove_pattern that simulates the removal of the given pattern using a stack. It loops through each character and checks whether the top of the stack and the current character form the desired pattern. If they do, I remove the top and add the pattern’s value to the score. I run this function twice: once for the higher-value pattern and again for the other on the updated string.

Implementation

class Solution:
    def maximumGain(self, s: str, x: int, y: int) -> int:
        def remove_pattern(s: str, first: str, second: str, value: int) -> (str, int):
            stack = []
            score = 0
            for char in s:
                if stack and stack[-1] == first and char == second:
                    stack.pop()
                    score += value
                else:
                    stack.append(char)
            return ''.join(stack), score

        total = 0
        
        if x > y:
            s, gain_x = remove_pattern(s, 'a', 'b', x)
            s, gain_y = remove_pattern(s, 'b', 'a', y)
        else:
            s, gain_y = remove_pattern(s, 'b', 'a', y)
            s, gain_x = remove_pattern(s, 'a', 'b', x)
        return gain_x + gain_y

Complexities

• Time: O(n)
• Space: O(n)