[Leetcode] 1717. Maximum Score From Removing Substrings

https://leetcode.com/problems/maximum-score-from-removing-substrings/description/?envType=daily-question&envId=2025-07-23

initial

so I thought of pattern on pen and paper and got it! im thinking like stack way iterating twice where
if y>x, high priority = 'a' and low priority='a'. for first iteration if current character is high_prioirity we see if stack[-1] is low prioirty then we pop and add value
then i think the bigger value operation is all done so i iterate stack again and see if there is any low value pattern in it? That is exactly right

sol

for the second pass, I didnt really know how to implement like do i iterate through the original stack and use a separate pointer? But we can just create a new stack list and as we iterate through the old stack, we push and pop onto the new stack. That simplifies things instead of trying to just work on the original stack

class Solution:
    def maximumGain(self, s: str, x: int, y: int) -> int:
        if y>x:
            high="a"
            low="b"
            high_score=y
            low_score=x
        else:
            high="b"
            low="a"
            high_score=x
            low_score=y
        ans=0
        stack=[]
        for i in s:
            if i==high:
                if stack and stack[-1]==low:
                    stack.pop()
                    ans+=high_score
                else:
                    stack.append(i)
            else:
                stack.append(i)
        new_stack=[]
        for idx in range(len(stack)):
            if stack[idx]==low:
                if new_stack and new_stack[-1]==high:
                    new_stack.pop()
                    ans+=low_score
                else:
                    new_stack.append(stack[idx])
            else:
                new_stack.append(stack[idx])
        return ans

complexity

n time n space