We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Check If Word Is Valid After Substitutions

Number: 1045

Difficulty: Medium

Paid? No

Companies: Amazon, Adobe, Nutanix

Problem Description

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 by repeatedly inserting the substring "abc" at any position.

Key Insights

  • The problem can be solved by simulating the reversal of the insertion process.
  • Use a stack to process characters one by one.
  • Whenever the last three characters in the stack form the substring "abc", remove them as they represent a valid insertion.
  • The string is valid if, after processing all characters, the stack is empty.

Space and Time Complexity

Time Complexity: O(n), where n is the length of s since we process each character once. Space Complexity: O(n) in the worst case when the stack holds all characters.

Solution

We use a stack to remove any complete occurrences of "abc". As we iterate over the string, each character is pushed onto the stack. Whenever the top three characters form the substring "abc", they are popped out of the stack. The final string is valid only if the stack is empty after processing.

Code Solutions

# Python solution for checking if the word is valid after substitutions.

def isValid(s: str) -> bool:
    stack = []  # Initialize an empty stack.
    
    # Process each character in the string.
    for char in s:
        stack.append(char)  # Push current character onto the stack.
        # Check if the top three characters form "abc".
        if len(stack) >= 3 and stack[-3] == 'a' and stack[-2] == 'b' and stack[-1] == 'c':
            # Pop out the pattern "abc".
            stack.pop()
            stack.pop()
            stack.pop()
    
    # Return True if the stack is empty, indicating a valid string.
    return not stack

# Example usage:
# print(isValid("aabcbc"))  # Expected output: True
← Back to All Questions