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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Check If Word Is Valid After Substitutions

Difficulty: Medium

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 after performing the operation of inserting "abc" into any position in t any number of times.

Key Insights

  • The string can only be constructed by inserting "abc" repeatedly.
  • The order of characters must follow the pattern of "abc".
  • We can use a stack to simulate the valid construction of the string.

Space and Time Complexity

Time Complexity: O(n) - where n is the length of the string s, as we iterate through the string once. Space Complexity: O(n) - in the worst case, we may store all characters in the stack.

Solution

To solve the problem, we can utilize a stack data structure. We will iterate through the string and push characters onto the stack. Whenever we have three characters on the stack, we check if they form the string "abc". If they do, we pop them off the stack. At the end of the iteration, if the stack is empty, the string is valid; otherwise, it is not.

Code Solutions

def isValid(s: str) -> bool:
    stack = []
    for char in s:
        stack.append(char)  # Push current character onto the stack
        # Check if the last three characters form "abc"
        if len(stack) >= 3 and stack[-3:] == ['a', 'b', 'c']:
            stack.pop()  # Remove 'c'
            stack.pop()  # Remove 'b'
            stack.pop()  # Remove 'a'
    return len(stack) == 0  # If stack is empty, it's valid
← Back to All Questions