Domain 2MediumMEDIUM

Check If Word Is Valid After Substitutions

Determine if a string can be reduced to empty by repeatedly removing 'abc' substrings using a stack-based greedy reduction strategy.

Domain: medium•Updated: 2026-09-06
#stack#string manipulation#O(N)#linear space

Problem Breakdown

Restatement: We are given a string s composed of characters ‘a’, ‘b’, and ‘c’. A string is considered valid if it can be constructed starting from an empty string by repeatedly inserting the substring “abc” anywhere. Conversely, this implies that any valid string must contain at least one instance of “abc”, which we could remove to reveal a smaller valid string (or reach an empty state).

Inputs:

  • s: A string containing only ‘a’, ‘b’, and ‘c’. Length between 1 and 2⋅1042 \cdot 10^4.

Outputs:

  • Boolean: True if reducible to empty, False otherwise.

Implicit Constraints & Edge Cases:

  • Order Dependency: The characters must appear in the sequence “abc” relative to each other (nested or adjacent). Simply counting ‘a’, ‘b’, and ‘c’ is insufficient because order matters (abccba has equal counts but invalid structure).
  • Nested Structures: Valid strings can be nested, e.g., aabcbc. The innermost “abc” must be removed first conceptually.
  • Empty Result: If the stack reduces to empty at the end of processing, it is valid.

Intuition

Brute Force Approach (Rejected): We could try all possible insertion points for every operation or simulate building up from scratch by trying all permutations of “abc” insertions. This would be exponential in complexity (O(2N)O(2^N) or worse) because the number of ways to place substrings grows rapidly with length.

Key Insight: The problem is symmetric regarding operations. If we can build s by inserting “abc”, then removing any existing instance of “abc” from a valid string must also yield another valid string (or empty). Therefore, instead of building up, we should try to reduce down. We scan the string and greedily remove every occurrence of “abc”.

Optimal Approach: A Stack is ideal for this pattern matching. As we iterate through s, we push characters onto a stack. Whenever the top three elements form “abc”, it means we found an insertion point that was validly added, so we pop them off (effectively reversing the operation). If at any point we encounter ‘c’ but don’t have preceding ‘a’, ‘b’ on the stack to complete the triplet, or if characters are out of order, they remain. Finally, a valid string must reduce the entire stack to empty.

Approach

  1. Initialize an empty list stack (acting as our data structure).
  2. Iterate through each character char in input string s.
  3. Push char onto stack.
  4. After pushing, check if the last three elements of stack match “abc”.
    • Condition: Length ≥\ge 3 AND stack[-1] == 'c', stack[-2] == 'b', stack[-3] == 'a'.
  5. If they match, pop all three characters from the stack (remove them).
  6. After iterating through the entire string, check if stack is empty.
    • Empty →\rightarrow Return True.
    • Not Empty →\rightarrow Return False.

Complexity Analysis

  • Time Complexity: O(N)O(N) where NN is the length of s. We iterate through each character exactly once (O(1)O(1) work per iteration). The stack operations (push/pop) are amortized constant time. Checking the top 3 elements involves a fixed-size slice check, which is effectively O(1)O(1).
  • Space Complexity: O(N)O(N) in the worst case where no “abc” patterns exist to reduce the string (e.g., input aaaa...). The stack stores up to all characters of s.

Solution

def isValid(s: str) -> bool:
    """
    Determines if a valid word can be formed by inserting 'abc' repeatedly.
    
    Args:
        s (str): Input string containing only 'a', 'b', and 'c'.
        
    Returns:
        bool: True if the string is valid, False otherwise.
    """
    stack = []
    
    for char in s:
        # Push current character onto the stack
        stack.append(char)
        
        # Check if we have completed an "abc" pattern at the top of the stack
        # We need to ensure there are enough elements before checking content
        if len(stack) >= 3 and \
           stack[-1] == 'c' and \
           stack[-2] == 'b' and \
           stack[-3] == 'a':
            # Remove the matched "abc" pattern (reverse insertion operation)
            del stack[-3:]

    return len(stack) == 0