LeetCode 1003: Check If Word Is Valid After Substitutions

Problem Restatement

We are given a string s.

A string is valid if we can repeatedly remove the substring "abc" from it until the string becomes empty.

We need to return true if s is valid, and false otherwise.

The official constraints state that 1 <= s.length <= 2 * 10^4 and s consists only of letters a, b, and c.

Input and Output

Function shape:

def isValid(s: str) -> bool:
    ...

Examples

Example 1:

s = "aabcbc"

Remove "abc" from positions 1-3: "aabcbc" → "abc" → ""

Answer:

True

Example 2:

s = "abcabcababcc"

Remove leftmost "abc": "abcabcababcc" → "abcababcc" → "ababcc" → "abcc" → "abc" → ""

Answer:

True

Example 3:

s = "abccba"

No "abc" substring remains after any step without creating a dead end.

Answer:

False

Key Insight

We can use a stack to simulate the removal process without repeatedly scanning the string.

Push characters onto the stack one at a time.

Whenever the top three characters of the stack are "a", "b", "c" (from bottom to top), pop all three.

This works because "abc" must be contiguous, and the stack naturally simulates the removal in the right order.

Algorithm

1. Initialize an empty stack.
2. For each character ch in s:
   • Push ch.
   • If the top three stack elements are ['a', 'b', 'c'], pop all three.
3. Return true if the stack is empty.

Correctness

When we push a character and the top three stack elements form "abc", this means the last three characters of the string processed so far form "abc". Removing them is correct because they are contiguous.

After this removal, the characters below them in the stack are revealed. If they also form "abc" now, the next iteration of the same step handles them.

Since every valid string reduces to empty via repeated "abc" removals, and the stack processes each removal in left-to-right order, the stack approach correctly identifies all valid strings.

An invalid string leaves leftover characters in the stack.

Edge Cases

• The stack should store exactly the unresolved items needed by the invariant.
• Process equal values deliberately; many monotonic-stack problems differ only in < versus <=.
• Flush or inspect the remaining stack after the scan if unresolved items still contribute to the answer.

Complexity

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []

        for ch in s:
            stack.append(ch)

            if len(stack) >= 3 and stack[-3:] == ['a', 'b', 'c']:
                stack.pop()
                stack.pop()
                stack.pop()

        return len(stack) == 0

Code Explanation

We process each character by pushing it:

stack.append(ch)

After each push, check if the top three form "abc":

if len(stack) >= 3 and stack[-3:] == ['a', 'b', 'c']:
    stack.pop()
    stack.pop()
    stack.pop()

If the stack is empty at the end, all characters were removed via valid "abc" deletions:

return len(stack) == 0

Testing

def run_tests():
    s = Solution()

    assert s.isValid("aabcbc") == True
    assert s.isValid("abcabcababcc") == True
    assert s.isValid("abccba") == False
    assert s.isValid("abc") == True
    assert s.isValid("ab") == False
    assert s.isValid("aabbcc") == False

    print("all tests passed")

run_tests()