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:
"abc" into any position in t. More formally, t becomes tleft + "abc" + tright, where t == tleft + tright. Note that tleft and tright may 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 * 104s consists of letters 'a', 'b', and 'c'In #1003 Check If Word Is Valid After Substitutions, a string is considered valid if it can be reduced to an empty string by repeatedly replacing the substring "abc" with an empty string. The key observation is that every valid construction must follow the exact order a → b → c. This pattern makes a stack-based approach very effective.
Traverse the string character by character and push characters onto a stack. Whenever you encounter 'c', check if the top of the stack forms the sequence 'a' followed by 'b'. If so, remove them along with the current 'c', effectively simulating the removal of "abc". If the pattern does not match, the string cannot be valid.
At the end of the traversal, the string is valid only if the stack becomes empty. This approach works because it mimics the substitution process while scanning the string once. The algorithm runs in O(n) time with O(n) auxiliary space for the stack.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Stack-based pattern validation | O(n) | O(n) |
AlgosWithMichael
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The stack works because valid strings must always build the pattern "abc" in order. By pushing characters and validating when 'c' appears, the stack effectively simulates the step-by-step substitution process.
Yes, variations of this problem can appear in technical interviews at companies like Amazon, Google, and Meta. It tests understanding of stack-based string processing and pattern validation, which are common interview topics.
A stack is the most suitable data structure because it naturally supports checking the most recent characters in sequence. This allows the algorithm to efficiently verify whether the latest characters form the required "abc" pattern.
The optimal approach uses a stack to simulate the removal of the substring "abc" while scanning the string. When a 'c' appears, the algorithm checks whether the previous characters form 'a' and 'b'. If they do, they are removed from the stack, effectively validating the substitution pattern.