Check If Word Is Valid After Substitutions - Solution & Explanation
Problem Statement
Given a string s, determine if it is valid.
A string s is valid if, starting with an empty string t = "", you can transform t into s after performing the following operation any number of times:
- Insert string
"abc"into any position int. More formally,tbecomestleft + "abc" + tright, wheret == tleft + tright. Note thattleftandtrightmay be empty.
Return true if s is a valid string, otherwise, return false.
Example 1:
Input: s = "aabcbc" Output: true Explanation: "" -> "abc" -> "aabcbc" Thus, "aabcbc" is valid.
Example 2:
Input: s = "abcabcababcc" Output: true Explanation: "" -> "abc" -> "abcabc" -> "abcabcabc" -> "abcabcababcc" Thus, "abcabcababcc" is valid.
Example 3:
Input: s = "abccba" Output: false Explanation: It is impossible to get "abccba" using the operation.
Constraints:
1 <= s.length <= 2 * 104sconsists of letters'a','b', and'c'
Approach Overview
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.
Approach 1: Stack-Based Approach for Validation
This approach leverages a stack data structure to validate the string. The main idea is to iterate over each character in the string and utilize the stack to check for the sequence 'abc'. When 'abc' is encountered, it is removed from the stack, simulating the reverse operation of building the string with 'abc'. If the stack is empty after processing all characters, the string is valid.
The function uses a stack to keep track of characters as we iterate through the string. Whenever the last three characters in the stack form the sequence 'abc', they are removed from the stack. The function returns true if the stack is empty at the end, indicating that the string can be completely reduced by removing 'abc' sequences.
Complexity
Time Complexity: O(n) where n is the length of the string because we process each character once.
Space Complexity: O(n) in the worst case where the stack might store all characters if no 'abc' sequence is found.
Approach 2: String Replacement Iteration
This approach involves iteratively searching for and replacing occurrences of the substring 'abc' in the string until no more are found. If the final string is empty, it suggests all parts of the string have been validly constructed using 'abc'.
This JavaScript solution iteratively replaces occurrences of 'abc' in the string. By continually replacing 'abc' with an empty string until no more replacements can be made, it checks if the resulting string is empty. An empty result means the original string was valid.
Code
JavaScript
C#
Complexity
Time Complexity: O(n^2) because each replacement operation may scan the entire string.
Space Complexity: O(n) for storing substrings temporarily during operations.
Approach 3: Stack
We observe the operations in the problem and find that each time a string "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 false.
Next, we traverse each character c in the string s. We first push the character c onto the stack t. If the length of the stack t is greater than or equal to 3, and the top three elements of the stack form the string "abc", then we pop the top three elements from the stack. We then continue to traverse the next character in the string s.
After the traversal, if the stack t is empty, it means the string s is valid, and we return true; otherwise, we return false.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string s.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Stack-Based Approach for Validation | Time Complexity: O(n) where n is the length of the string because we process each character once. |
| String Replacement Iteration | Time Complexity: O(n^2) because each replacement operation may scan the entire string. |
| Stack | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack-Based Validation | O(n) | O(n) | Best general solution. Efficient single-pass validation for large strings. |
| String Replacement Iteration | O(n^2) | O(n) | Useful for understanding the construction rule or quick scripting solutions. |
Video Solution
Check If Word Is Valid After Insertion | Check If Word Is Valid After Substitutions | Leetcode 1003 • Pepcoding • 4,300 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Check If Word Is Valid After Substitutions easy or hard?
Check If Word Is Valid After Substitutions Python/Java solution
How to solve Check If Word Is Valid After Substitutions in O(n)?
What is the best approach for Check If Word Is Valid After Substitutions?
Is Check If Word Is Valid After Substitutions asked at Google/Amazon/Meta?
What data structure is used in Check If Word Is Valid After Substitutions?
What is the time complexity of Check If Word Is Valid After Substitutions?
Ready to solve this problem?
Practice Check If Word Is Valid After Substitutions with our built-in code editor and test cases.
Practice on FleetCode