#1003

Medium

auto_awesomeStack-based state management

LeetCode Problem Workspace

Check If Word Is Valid After Substitutions

Determine if a string can be built from repeated 'abc' insertions using stack-based state management, verifying sequence correctness.

string stack

Problem Statement

Given a string s consisting only of the letters 'a', 'b', and 'c', determine whether it is a valid string after a series of substitutions. A string is valid if it can be built by repeatedly inserting the substring 'abc' into an empty string.

Return true if the string is valid according to this rule, otherwise return false. Examples include s = "aabcbc" which is valid because it can be constructed as "" -> "abc" -> "aabcbc", and s = "abccba" which is invalid since no sequence of 'abc' insertions produces it.

Examples

Example 1

Input: s = "aabcbc"

Output: true

"" -> "abc" -> "aabcbc" Thus, "aabcbc" is valid.

Example 2

Input: s = "abcabcababcc"

Output: true

"" -> "abc" -> "abcabc" -> "abcabcabc" -> "abcabcababcc" Thus, "abcabcababcc" is valid.

Example 3

Input: s = "abccba"

Output: false

It is impossible to get "abccba" using the operation.

Constraints

1 <= s.length <= 2 * 104
s consists of letters 'a', 'b', and 'c'

Solution Approach

Use a Stack to Track Characters

Iterate through the string and push each character onto a stack. Whenever the top three elements form 'abc', pop them off. This ensures that only valid 'abc' sequences remain on the stack.

Validate Remaining Stack

After processing the entire string, check if the stack is empty. An empty stack confirms that all characters were part of valid 'abc' sequences, otherwise the string is invalid.

Optimize for Linear Time

Since each character is pushed and popped at most once, this stack approach runs in O(n) time with O(n) space. It efficiently handles all valid and invalid patterns without backtracking.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) since each character is processed once. Space complexity is O(n) due to the stack storing characters for partial 'abc' sequences.

What Interviewers Usually Probe

Focuses on stack-based state validation rather than brute force generation.
Checks understanding of sequence pattern enforcement with linear space.
Wants confirmation of handling edge cases where sequences overlap or are incomplete.

Common Pitfalls or Variants

Common pitfalls

Failing to remove completed 'abc' sequences properly from the stack.
Assuming any permutation of 'abc' is valid instead of the exact order.
Not handling overlapping sequences like 'aabcbc' correctly.

Follow-up variants

Check if string is valid with a different fixed substring instead of 'abc'.
Allow nested or overlapping insertion rules and validate resulting string.
Count how many valid 'abc' sequences exist instead of boolean validation.

FAQ

What does 'Check If Word Is Valid After Substitutions' mean?

It means verifying if a string can be built by repeatedly inserting the substring 'abc' into an empty string.

Why use a stack for this problem?

A stack tracks the current sequence and allows immediate removal of valid 'abc' sequences, ensuring order correctness.

Can any permutation of 'abc' be considered valid?

No, only the exact order 'a', 'b', 'c' in sequence is valid; other orders break the pattern.

What if the input string contains characters other than 'a', 'b', 'c'?

According to the constraints, the input will only contain 'a', 'b', and 'c', so other characters are not allowed.

How does GhostInterview help in solving this problem?

It walks through the stack-based validation pattern, points out where sequences fail, and confirms linear-time correctness.

terminal

Solution

Solution 1: Stack

We observe the operations in the problem and find that each time a string $\textit{"abc"}$ is inserted at any position in the string. Therefore, after each insertion operation, the length of the string increases by $3$. If the string $s$ is valid, its length must be a multiple of $3$. Thus, we first check the length of the string $s$. If it is not a multiple of $3$, then $s$ must be invalid, and we can directly return $\textit{false}$.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 3:
            return False
        t = []
        for c in s:
            t.append(c)
            if ''.join(t[-3:]) == 'abc':
                t[-3:] = []
        return not t

Continue Practicing

#1021 remove outermost parentheses #1047 remove all adjacent duplicates in string #936 stamping the sequence