Check If Word Is Valid After Substitutions

Check If Word Is Valid After Substitutions

What is this problem about?

A string s is valid if it can be formed by starting with an empty string and repeatedly inserting the string "abc" at any position. For example, "" -> "abc" -> "aabcbc". Given a string, you need to determine if it is valid under these rules.

Why is this asked in interviews?

Companies like Amazon and Nutanix use this to test your understanding of Stack-based parsing. It’s a variation of the "Valid Parentheses" problem. Instead of a single character match, you are looking for a sequence match ("abc"). It evaluations your ability to identify and remove patterns from the "top" of a stack as you build it.

Algorithmic pattern used

The pattern is the Stack interview pattern. You iterate through the characters of the string one by one and push them onto a stack. Whenever the top three characters of the stack form "abc", you pop them off. If the string is valid, the stack will be empty at the end.

Example explanation

String: "aabcbc"

1. Push 'a', 'a', 'b'. Stack: ['a', 'a', 'b'].
2. Next is 'c'. The top of the stack + 'c' is "abc". Pop 'a', 'b', 'c'. Stack: ['a'].
3. Next is 'b'. Stack: ['a', 'b'].
4. Next is 'c'. Top of stack + 'c' is "abc". Pop 'a', 'b', 'c'. Stack: []. End of string, stack is empty. Result: True.

Common mistakes candidates make

The most common mistake is using string replacement (s.replace("abc", "")) in a loop. While this works for some cases, it can be $O(N^2)$ in the worst case and might not handle all edge cases correctly. Another mistake is not checking the order of characters in the stack (e.g., "bac" should not be popped).

Interview preparation tip

Whenever you see a problem about "repeatedly removing a specific substring," think about using a stack. A stack allows you to handle nested removals in linear time, whereas string manipulation often leads to quadratic complexity.