Check If Word Is Valid After Substitutions: Stack Reduction

Check If Word Is Valid After Substitutions is LeetCode 1003, rated Medium. It is a neat problem that disguises a stack pattern behind string manipulation. Once you see the trick, the solution is clean and fast.

The problem

You start with an empty string. At each step, you can insert the substring "abc" at any position in the current string. A string s is valid if and only if it can be built by repeating this process.

Given a string s, return true if it is valid, and false otherwise.

Examples:

• "aabcbc" is valid. Start with "", insert "abc" to get "abc", then insert "abc" at position 1 to get "aabcbc".
• "abcabcababcc" is valid. You can build it by inserting "abc" four times in the right positions.
• "abccba" is not valid. No sequence of "abc" insertions can produce this string.
• "abc" is valid. One insertion does it.

The key insight is that every valid string, no matter how deeply nested the insertions are, can be "unwound" by repeatedly removing "abc" substrings until nothing is left.

Why a stack works

Think about what it means to insert "abc" at any position. You might insert it inside an existing "abc", splitting it apart. For example, inserting "abc" into position 1 of "abc" gives "aabcbc". The inner "abc" sits between the a and bc of the outer one.

This is a nesting structure, and nesting is exactly what stacks handle well.

The algorithm works like this:

1. Walk through the string character by character.
2. If the character is 'a' or 'b', push it onto the stack.
3. If the character is 'c', check whether the top two elements of the stack are 'b' (top) and then 'a' (second from top). If yes, pop both of them. This removes one complete "abc" from the string. If no, the string is invalid.
4. After processing every character, check if the stack is empty. If it is, the string is valid.

Every time you encounter a 'c', you are completing an "abc" triplet. The stack naturally handles the nesting because the most recently pushed 'a' and 'b' are always the ones that belong to the innermost "abc".

The code

Here is the Python solution for LeetCode 1003:

def is_valid(s: str) -> bool:
    stack = []

    for ch in s:
        if ch == 'c':
            if len(stack) < 2 or stack[-1] != 'b' or stack[-2] != 'a':
                return False
            stack.pop()
            stack.pop()
        else:
            stack.append(ch)

    return len(stack) == 0

Let's walk through what makes this work:

• When we see 'a' or 'b', we push it. No validation needed at this point because partial sequences are fine while we are still reading.
• When we see 'c', we check two things: does the stack have at least two elements, and are the top two 'b' then 'a' (reading from top to bottom)? If either check fails, the string cannot be valid.
• The two pop() calls remove the matched 'b' and 'a', effectively canceling out one "abc" substring.
• After all characters are processed, the stack must be empty. If anything remains, there were unmatched characters.

Visual walkthrough

Let's trace through "aabcbc" step by step. Watch how the stack grows when we push 'a' and 'b', and shrinks when 'c' triggers a match and removes an "abc" triplet.

Two "abc" substrings were removed. The stack ended empty. The string is valid.

Complexity analysis

Time: O(n). We iterate through the string once. Each character triggers at most one push or two pops, all O(1) operations. Total work is proportional to the length of the string.

Space: O(n). In the worst case, the string is something like "aaa...bbb..." with no 'c' characters, and we push every character onto the stack. Stack size can grow up to n.

The building blocks

Stack-based reduction

The core idea is treating the input as something you can reduce by removing matched patterns. Each time you find a complete "abc" at the top of the stack, you remove it and continue. This is the same concept behind bracket matching (remove matched pairs) and decode string (collapse nested structures).

The reduction pattern shows up whenever a problem asks "can this sequence be fully consumed by removing valid sub-patterns?" The stack keeps track of partial patterns in progress, and completions trigger pops.

Sequential character classification

The other building block is classifying each character into a role: 'a' and 'b' are state-building characters that get pushed, while 'c' is a trigger character that fires a validation-and-pop sequence. This classification-then-action pattern appears in expression parsing, calculator problems, and any problem where different characters drive different stack operations.

Edge cases to watch for

• Empty string. An empty string is valid per the problem definition (you start with empty and insert zero times). The code handles this because the loop does not execute and len(stack) == 0 returns True.
• Single "abc". The simplest valid string. Push 'a', push 'b', see 'c' and pop both. Stack is empty. Valid.
• Wrong order. "bac" or "cab" fail because when 'c' is encountered, the top two stack elements are not 'b' then 'a' in the right order.
• Extra characters at the end. "abcab" processes the "abc" fine but leaves ['a', 'b'] on the stack. The final len(stack) == 0 check catches this.
• Only 'c' characters. "ccc" fails immediately at the first 'c' because the stack is empty.
• Deeply nested. "aabcbc" or even "aaabcbcbc" work correctly because the stack peels off the innermost "abc" first, then the next layer, and so on.

From understanding to recall

The stack reduction for this problem is short. Push 'a' and 'b', pop when you see 'c', check if the stack is empty at the end. It all clicks once you see it. But three weeks from now, the details blur. Was it stack[-1] != 'a' or stack[-1] != 'b'? Do I pop once or twice?

These are not conceptual gaps. They are recall gaps. You understand the algorithm right now, but reproducing it from scratch under time pressure is a separate skill.

Spaced repetition fixes this. You write the solution from memory at increasing intervals. Each repetition reinforces the character checks, the pop order, and the empty-stack condition. After a few cycles, the whole thing is automatic. You do not second-guess the details because you have already written this code many times.

Related posts

• Valid Parentheses - The classic stack matching problem, using the same push-on-open, pop-on-close pattern
• Decode String - Stack-based string construction where nested structures get collapsed layer by layer
• Valid Parenthesis String - A trickier validation problem where wildcard characters add flexibility to the matching rules