Check If Word Is Valid After Substitutions - Video Solutions

Problem Overview: You receive a string s containing only the characters a, b, and c. The string is considered valid if it can be built by repeatedly inserting the substring "abc" into an empty string. The task is to check whether the given string could have been formed using only these insert operations.

Approach 1: Stack-Based Validation (O(n) time, O(n) space)

This approach processes the string left to right while simulating the construction rule using a stack. Push characters onto the stack as you iterate. Whenever the current character is c, check whether the top two elements of the stack form "ab". If they do, pop them and effectively remove the "abc" sequence. If the pattern does not match, the string cannot be valid. This works because every valid string is composed of nested or sequential "abc" blocks, and the stack naturally tracks unfinished prefixes. The algorithm performs a single pass through the string, giving O(n) time complexity and O(n) auxiliary space for the stack.

This solution relies heavily on a stack to validate structure as characters arrive. It mirrors how compilers validate nested patterns and works well for streaming-style validation where you cannot repeatedly rebuild the string.

Approach 2: String Replacement Iteration (O(n^2) time, O(n) space)

A more intuitive strategy repeatedly removes occurrences of "abc" from the string until no more replacements are possible. Each iteration scans the string and replaces every "abc" with an empty string. If the string eventually becomes empty, it was valid; otherwise, leftover characters indicate an invalid structure. The idea works because valid strings are fully reducible through these substitutions.

The downside is performance. Each replacement may require rebuilding the string, and the process may run multiple passes over the input. In the worst case this leads to O(n^2) time complexity while using O(n) space to hold intermediate strings. Despite the inefficiency, the method is easy to implement and helpful when reasoning about how the grammar expands and contracts.

This approach mainly involves repeated scanning and manipulation of a string. It is straightforward but less efficient compared to a stack-driven solution.

Recommended for interviews: The stack-based solution is the expected answer. It processes the string in one pass and demonstrates strong understanding of pattern validation using stacks. Mentioning the replacement idea first can help show intuition about the problem’s construction rule, but interviewers typically look for the linear-time stack implementation because it scales to large inputs.