Leetcode 1003. Check If Word Is Valid After Substitutions

Problem statement

https://leetcode.com/problems/check-if-word-is-valid-after-substitutions/

Solution

We need to use stack: when we have a b c in the end of stack, remove it while we can.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def isValid(self, s):
        stack = []
        for x in s:  
            stack += [x]
            while len(stack) >= 3 and stack[-3:] == ["a", "b", "c"]:
                for _ in range(3): stack.pop()
            
        return not stack