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 .
Outputs:
- Boolean:
Trueif reducible to empty,Falseotherwise.
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 (
abccbahas 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 ( 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
- Initialize an empty list
stack(acting as our data structure). - Iterate through each character
charin input strings. - Push
charontostack. - After pushing, check if the last three elements of
stackmatch “abc”.- Condition: Length 3 AND
stack[-1] == 'c',stack[-2] == 'b',stack[-3] == 'a'.
- Condition: Length 3 AND
- If they match, pop all three characters from the stack (remove them).
- After iterating through the entire string, check if
stackis empty.- Empty Return
True. - Not Empty Return
False.
- Empty Return
Complexity Analysis
- Time Complexity: where is the length of
s. We iterate through each character exactly once ( 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 . - Space Complexity: in the worst case where no “abc” patterns exist to reduce the string (e.g., input
aaaa...). The stack stores up to all characters ofs.
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