Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The two removable patterns compete only where they overlap, as in aba or bab. Removing either overlapping pair leaves the same single letter, so choosing the higher-scoring pair first never hurts future opportunities. Other characters separate independent regions.

Approach

Choose ab first if its score exceeds ba's; otherwise choose ba. Scan with a stack: when its top and the current character form the chosen pair, pop and earn the score; otherwise push the character. Reconstruct the remaining string and run the same process for the other pattern. Sum both passes. The stack automatically detects new adjacent pairs exposed by earlier removals, and either order is valid when scores tie.

class Solution:
    def maximumGain(self, s: str, x: int, y: int) -> int:
        self.s = s
        op = 'ab' if x > y else 'ba'

        def solve(op):
            res = 0
            stack = []

            for i in range(len(self.s)):
                if not stack or stack[-1] != op[0] or self.s[i] != op[1]:
                    stack.append(self.s[i])
                else:
                    stack.pop()
                    res += x if op == 'ab' else y

            self.s = "".join(stack)
            return res

        out = solve(op)
        op = 'ab' if op == 'ba' else 'ba'
        out += solve(op)

        return out

Complexity analysis

Let n = s.length. Time: O(n) across the two stack passes. Auxiliary space: O(n) for the stack/string remaining between passes.