LeetCode 1003 - Check If Word Is Valid After Substitutions

The problem asks us to determine whether a given string can be constructed by repeatedly inserting the substring "abc" into an initially empty string. The operation is very specific. At any point, we may take the current string and insert "abc" at any position.

leetcodemediumstringstack

LeetCode Problem 1003

Difficulty: šŸŸ” Medium
Topics: String, Stack

Solution

Problem Understanding

The problem asks us to determine whether a given string can be constructed by repeatedly inserting the substring "abc" into an initially empty string.

The operation is very specific. At any point, we may take the current string and insert "abc" at any position. Because insertion can happen anywhere, valid strings may contain nested or interleaved patterns that are not immediately obvious.

For example:

  • Starting from ""
  • Insert "abc" ā†’ "abc"
  • Insert "abc" in the middle ā†’ "aabcbc"

The input consists only of the characters 'a', 'b', and 'c', and the string length can be as large as 2 * 10^4. This immediately suggests that exponential or repeatedly rescanning approaches may become too slow.

The expected output is:

  • true if the string can be formed entirely through valid "abc" insertions
  • false otherwise

An important observation is that every valid insertion ultimately creates groups that reduce back to "abc". If we can repeatedly identify and remove "abc" patterns until nothing remains, then the string is valid.

Several edge cases are important:

  • Strings whose length is not divisible by 3 can never be valid, because every operation adds exactly 3 characters.
  • Strings that contain characters in the wrong order, such as "acb" or "abccba", must return false.
  • Strings with incomplete sequences like "ab" or "aabbcc" are invalid.
  • Nested constructions like "aabcbc" or "abcabcababcc" must still be recognized as valid.

The challenge is efficiently validating the structure without generating all possible insertion sequences.

Approaches

Brute Force Approach

A straightforward approach is to repeatedly search for occurrences of "abc" in the string and remove them.

For example:

  • "aabcbc"
  • remove "abc" ā†’ "abc"
  • remove "abc" ā†’ ""

If the string eventually becomes empty, then it is valid.

This works because every valid string is composed of inserted "abc" blocks, so reversing the process by deleting "abc" repeatedly reconstructs the empty string.

However, this approach is inefficient. Each removal may require scanning the entire string, and string reconstruction itself is expensive because strings are immutable in many languages. In the worst case, we may perform many scans and many rebuild operations.

With a maximum length of 20,000, repeated full-string operations can degrade toward quadratic time complexity.

Optimal Approach

The key insight is that valid strings always form "abc" patterns incrementally.

Instead of repeatedly removing substrings from the whole string, we can process the string from left to right using a stack.

The idea is:

  • Push characters onto the stack.
  • Whenever the top three characters become "abc", remove them immediately.

This simulates reducing valid constructions as soon as they appear.

For example:

  • Read 'a' ā†’ stack = ['a']
  • Read 'b' ā†’ stack = ['a', 'b']
  • Read 'c' ā†’ stack = ['a', 'b', 'c']
  • Top is "abc" ā†’ pop all three
  • Stack becomes empty

If the entire string is processed and the stack is empty, then every character participated in a valid "abc" sequence.

This approach processes each character once and performs only constant-time stack operations.

Approach Time Complexity Space Complexity Notes
Brute Force O(nĀ²) O(n) Repeatedly searches and removes "abc" substrings
Optimal O(n) O(n) Uses a stack to reduce valid "abc" groups immediately

Algorithm Walkthrough

  1. Initialize an empty stack.

The stack stores characters that have not yet formed a complete "abc" sequence. 2. Iterate through each character in the string.

We process the string left to right because valid sequences are built incrementally. 3. Push the current character onto the stack.

Every character is temporarily stored until we know whether it completes a valid pattern. 4. After pushing, check whether the top three stack elements are "a", "b", and "c".

This is the critical step. Whenever a valid sequence forms, we immediately remove it. This mimics reversing one insertion operation. 5. If the top three characters form "abc", pop them from the stack.

Removing them keeps the stack representing only unresolved characters. 6. Continue until all characters are processed. 7. At the end, check whether the stack is empty.

If it is empty, every character participated in a valid "abc" sequence. Otherwise, some invalid structure remains.

Why it works

The stack always maintains the portion of the string that has not yet been reduced into valid "abc" groups. Every time we encounter "abc" at the top of the stack, we remove it because that sequence corresponds exactly to one valid insertion operation.

If the string is valid, repeated reductions will eventually remove everything. If the string is invalid, some unmatched characters will remain in the stack.

This invariant guarantees correctness.

Python Solution

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

        for char in s:
            stack.append(char)

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

        return len(stack) == 0

The implementation closely follows the algorithm described earlier.

We begin by creating an empty stack. In Python, a list is ideal because append and pop operations from the end are both O(1).

As we iterate through each character:

  • The character is appended to the stack.
  • We then check whether the last three elements form "abc".

If they do, all three are removed immediately. This continuously reduces valid segments during traversal instead of waiting until the end.

Finally, we return whether the stack is empty. An empty stack means every character successfully formed part of a valid "abc" pattern.

Go Solution

func isValid(s string) bool {
    stack := make([]byte, 0)

    for i := 0; i < len(s); i++ {
        stack = append(stack, s[i])

        n := len(stack)

        if n >= 3 &&
            stack[n-3] == 'a' &&
            stack[n-2] == 'b' &&
            stack[n-1] == 'c' {

            stack = stack[:n-3]
        }
    }

    return len(stack) == 0
}

The Go implementation uses a byte slice as the stack because the input contains only ASCII characters.

Instead of calling pop() multiple times like Python, Go shortens the slice using:

stack = stack[:n-3]

This efficiently removes the last three elements.

Unlike Python, Go does not have a built-in stack type, but slices work perfectly for append and truncation operations.

Worked Examples

Example 1

Input:

s = "aabcbc"
Step Character Stack Before Stack After Action
1 a [] [a] push
2 a [a] [a, a] push
3 b [a, a] [a, a, b] push
4 c [a, a, b] [a] remove "abc"
5 b [a] [a, b] push
6 c [a, b] [] remove "abc"

Final stack is empty, therefore the string is valid.

Example 2

Input:

s = "abcabcababcc"
Step Character Stack State
1 a [a]
2 b [a, b]
3 c []
4 a [a]
5 b [a, b]
6 c []
7 a [a]
8 b [a, b]
9 a [a, b, a]
10 b [a, b, a, b]
11 c [a, b]
12 c []

Final stack is empty, so the string is valid.

Example 3

Input:

s = "abccba"
Step Character Stack State
1 a [a]
2 b [a, b]
3 c []
4 c [c]
5 b [c, b]
6 a [c, b, a]

The stack is not empty at the end, therefore the string is invalid.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each character is pushed once and popped at most once
Space O(n) The stack may hold all characters in the worst case

The algorithm is linear because every character participates in a constant number of stack operations. There are no nested scans or repeated substring searches.

The worst-case space usage occurs when no valid "abc" sequence can be reduced until the end, causing the stack to temporarily hold the entire string.

Test Cases

solution = Solution()

assert solution.isValid("abc") == True          # simplest valid case
assert solution.isValid("aabcbc") == True      # nested insertion
assert solution.isValid("abcabcababcc") == True  # complex valid nesting
assert solution.isValid("abccba") == False     # incorrect order
assert solution.isValid("ab") == False         # incomplete sequence
assert solution.isValid("cababc") == False     # invalid starting character
assert solution.isValid("aabbcc") == False     # grouped letters but invalid structure
assert solution.isValid("abcabc") == True      # multiple independent groups
assert solution.isValid("abcabcabc") == True   # repeated valid groups
assert solution.isValid("acb") == False        # wrong ordering
assert solution.isValid("bca") == False        # invalid arrangement
assert solution.isValid("c") == False          # single invalid character
assert solution.isValid("ababcc") == True      # nested reduction case
assert solution.isValid("") == True if False else True  # conceptual empty case
Test Why
"abc" Simplest valid string
"aabcbc" Tests nested insertion behavior
"abcabcababcc" Tests complex valid construction
"abccba" Tests invalid reversed structure
"ab" Tests incomplete sequence
"cababc" Tests invalid leading character
"aabbcc" Tests misleading grouped letters
"abcabc" Tests multiple separate valid groups
"abcabcabc" Tests repeated reductions
"acb" Tests incorrect ordering
"bca" Tests invalid permutation
"c" Tests smallest invalid input
"ababcc" Tests deeper nested reductions

Edge Cases

Length Not Divisible by Three

Every operation inserts exactly three characters. Therefore, any valid string must have a length divisible by 3.

Examples like "ab" or "abca" can never become valid. While the implementation does not explicitly check this condition, the stack naturally fails to reduce the entire string, leaving leftover characters.

Characters in Incorrect Order

Strings such as "acb" or "abccba" contain the correct letters but in an invalid arrangement.

A naive solution might incorrectly count character frequencies and assume validity. The stack approach avoids this mistake because it enforces exact sequential structure. Only contiguous "abc" formations are removed.

Nested Valid Constructions

Cases like "aabcbc" are tricky because the valid "abc" groups are not initially obvious.

The stack handles this naturally by reducing newly formed "abc" sequences as soon as they appear. This incremental reduction allows nested constructions to collapse correctly.

Residual Characters After Partial Reduction

Some strings partially reduce but still leave invalid remnants.

For example:

"abca"

The first "abc" reduces successfully, but one 'a' remains in the stack. The final empty-stack check correctly identifies the string as invalid.