{x}
blog image

Check If Word Is Valid After Substitutions

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 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 * 104
  • s consists of letters 'a', 'b', and 'c'

Solution Explanation: Check If Word Is Valid After Substitutions

This problem asks whether a given string s can be constructed by repeatedly inserting "abc" at any position within an initially empty string. The solution leverages a stack-based approach for efficient checking.

Approach:

  1. Length Check: A crucial observation is that if s is valid, its length must be a multiple of 3 (because each insertion adds three characters). The solution begins by checking this condition. If the length is not divisible by 3, the string is immediately invalid, and false is returned.

  2. Stack Traversal: A stack (t) is used to simulate the string construction process. The algorithm iterates through each character c of the input string s:

    • c is pushed onto the stack.
    • If the stack now contains at least three elements, and the top three elements form "abc" (checked using string slicing or similar methods), those three elements are popped from the stack. This simulates the removal of an "abc" substring that was previously inserted.

  3. Final Check: After processing all characters in s, if the stack t is empty, it implies that all "abc" substrings were successfully identified and removed, indicating that s is valid. A non-empty stack means some characters remain unmatched, making the string invalid.

Time and Space Complexity:

  • Time Complexity: O(n), where n is the length of the input string s. The algorithm iterates through the string once. Stack operations (push and pop) are O(1) on average.

  • Space Complexity: O(n) in the worst case. The stack t could potentially hold up to all characters of s if no "abc" subsequences are found early on.

Code Examples:

The provided code examples in Python, Java, C++, Go, and TypeScript all implement this stack-based approach. They differ slightly in syntax and data structure choices (using lists/arrays/strings for the stack), but the core logic remains consistent. For instance, the Python solution uses list slicing (t[-3:] = []) for concisely removing the "abc" sequence. The Java solution uses StringBuilder for efficient string manipulation. The other languages employ similar techniques adapted to their specific features.

Example Walkthrough (Python):

Let's trace the Python code with s = "aabcbc":

  1. len(s) % 3 == 0, so the length check passes.
  2. The stack t starts empty.
  3. 'a' is pushed: t = ['a']
  4. 'a' is pushed: t = ['a', 'a']
  5. 'b' is pushed: t = ['a', 'a', 'b']
  6. 'c' is pushed: t = ['a', 'a', 'b', 'c']. The condition ''.join(t[-3:]) == 'abc' is false.
  7. 'b' is pushed: t = ['a', 'a', 'b', 'c', 'b']
  8. 'c' is pushed: t = ['a', 'a', 'b', 'c', 'b', 'c']. The condition ''.join(t[-3:]) == 'abc' is true. t[-3:] = [] removes the last three elements. t = ['a', 'a'].
  9. The loop finishes. t is not empty. The code returns False.

However, with s = "abcabcababcc", the stack will become empty at the end, resulting in True (valid).

The key to understanding this solution is the efficient use of the stack to mirror the string construction process described in the problem statement and the early exit condition based on string length.