Jobs

Interviews

Discussions

Check If Word Is Valid After Substitutions

Medium

Asked by:

7 views

Topics:

ArraysStacksStrings

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 t_left + "abc" + t_right, where t == t_left + t_right. Note that t_left and t_right 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 * 10⁴
s consists of letters 'a', 'b', and 'c'

Try coding it in LeetCode

Check If Word Is Valid After Substitutions

Medium

Asked by:

7 views

Topics:

ArraysStacksStrings

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 t_left + "abc" + t_right, where t == t_left + t_right. Note that t_left and t_right 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 * 10⁴
s consists of letters 'a', 'b', and 'c'

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string only contain 'a', 'b', and 'c' characters, or can it contain other characters as well?
Is the input string guaranteed to be non-null and a valid string, or do I need to handle null or empty string inputs?
Can the input string have leading or trailing whitespace?
If the string is not valid, what should I return: null, an empty string, or a boolean `false`?
Are the substitutions case-sensitive, i.e., should I consider 'abc' to be the same as 'Abc'?

Brute Force Solution

Approach

The brute force method for this problem involves repeatedly trying to simplify the given string by removing instances of "abc". We continue removing "abc" until the string is either empty or no longer contains "abc". If the string becomes empty, it's valid; otherwise, it's not.

Here's how the algorithm would work step-by-step:

Look for the substring "abc" within the string.
If "abc" is found, remove it from the string. This creates a new, shorter string.
Repeat the process of looking for "abc" and removing it from the shortened string.
Continue this removal process until you can no longer find "abc" within the string.
Once you can't find "abc" anymore, check if the remaining string is empty. If it's empty, the original string was valid.
If the remaining string is not empty, then the original string was not valid.

Code Implementation

def is_valid_after_substitutions(input_string):
    modified_string = input_string

    while True:
        abc_index = modified_string.find("abc")

        # If 'abc' is not found, break out of the loop
        if abc_index == -1:
            break

        # Remove 'abc' from the string.
        modified_string = modified_string[:abc_index] + modified_string[abc_index+3:]

    # Check if the remaining string is empty.
    if len(modified_string) == 0:
        return True
    else:
        return False

Big(O) Analysis

Time Complexity

O(n^2) – The algorithm repeatedly searches for and removes "abc" from the string. In the worst case, the string might be structured in a way where removing one "abc" requires scanning almost the entire string to find the next occurrence. Since we might need to repeat this process close to n/3 times (where n is the length of the input string), and each find-and-remove operation potentially involves scanning a large portion of the string again (up to n), the overall time complexity becomes approximately (n/3) * n, simplifying to O(n^2).

Space Complexity

O(N) – The algorithm repeatedly modifies the input string by removing "abc" substrings, potentially creating new strings in each iteration. In the worst-case scenario, the string might consist of many interleaving "abc" sequences, leading to repeated string modifications that could result in creating temporary strings of size proportional to the input string's length, denoted as N. Therefore, the auxiliary space used for string manipulation can grow linearly with the input size N. Consequently, the space complexity is O(N).

Optimal Solution

Approach

The key idea is to repeatedly simplify the input string by removing the pattern "abc". We use a stack to keep track of the characters we've seen so far, and whenever we find "abc" on top of the stack, we remove it.

Here's how the algorithm would work step-by-step:

Imagine you have a stack of characters.
Go through the input string one character at a time.
For each character, add it to the top of the stack.
Now, check if the top three characters in the stack form the sequence 'abc'.
If they do form 'abc', remove those three characters from the stack because they cancel each other out according to the rules.
If they don't form 'abc', just move on to the next character in the input string.
Keep doing this until you've processed the entire input string.
At the end, if the stack is empty, it means the entire input string was valid and could be reduced to nothing. Otherwise, it's not a valid string.

Code Implementation

def is_valid_after_substitutions(input_string):
    character_stack = []

    for character in input_string:
        character_stack.append(character)

        # Check for 'abc' sequence on top of stack.
        if len(character_stack) >= 3 and \
           character_stack[-3] == 'a' and \
           character_stack[-2] == 'b' and \
           character_stack[-1] == 'c':

            # Remove 'abc' from the stack.
            character_stack.pop()
            character_stack.pop()
            character_stack.pop()

    # If the stack is empty, the string is valid.
    return not character_stack

Big(O) Analysis

Time Complexity

O(n) – We iterate through the input string of length n once. Inside the loop, we perform constant-time operations: pushing a character onto the stack and checking the top three elements of the stack. The stack operations (push and pop) are also constant time. Since the number of iterations is directly proportional to the length of the string, the time complexity is O(n).

Space Complexity

O(N) – The provided solution uses a stack to store characters from the input string. In the worst-case scenario, if the input string doesn't contain any "abc" sequences, all N characters of the string will be pushed onto the stack. Therefore, the stack's size can grow linearly with the input size N. The auxiliary space is thus proportional to the size of the stack, leading to a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty input string	Return true if the string is null or empty because an empty string is considered valid after zero substitutions.
Input string is 'abc'	Return true because 'abc' represents a single 'abc' substitution.
Input string is 'ababcbc'	Return true; this is a valid sequence of substitutions.
Input string contains characters other than 'a', 'b', or 'c'	Return false immediately as these characters make it invalid per the problem definition.
Input string starts or ends with 'b' or 'c'	Return false immediately because the first 'abc' insertion always begins with 'a'.
Maximum input string size (considering potential stack overflow with recursion)	An iterative approach is required to handle large input strings and avoid stack overflow.
Input string contains uneven distribution of 'a', 'b', and 'c'	The algorithm should handle cases where the counts of 'a', 'b', and 'c' are not balanced, resulting in false.
Input string is 'abccba'	Return false; 'abc' can only be substituted if in sequence.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string only contain 'a', 'b', and 'c' characters, or can it contain other characters as well?
Is the input string guaranteed to be non-null and a valid string, or do I need to handle null or empty string inputs?
Can the input string have leading or trailing whitespace?
If the string is not valid, what should I return: null, an empty string, or a boolean `false`?
Are the substitutions case-sensitive, i.e., should I consider 'abc' to be the same as 'Abc'?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Look for the substring "abc" within the string.
If "abc" is found, remove it from the string. This creates a new, shorter string.
Repeat the process of looking for "abc" and removing it from the shortened string.
Continue this removal process until you can no longer find "abc" within the string.
Once you can't find "abc" anymore, check if the remaining string is empty. If it's empty, the original string was valid.
If the remaining string is not empty, then the original string was not valid.

Code Implementation

def is_valid_after_substitutions(input_string):
    modified_string = input_string

    while True:
        abc_index = modified_string.find("abc")

        # If 'abc' is not found, break out of the loop
        if abc_index == -1:
            break

        # Remove 'abc' from the string.
        modified_string = modified_string[:abc_index] + modified_string[abc_index+3:]

    # Check if the remaining string is empty.
    if len(modified_string) == 0:
        return True
    else:
        return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine you have a stack of characters.
Go through the input string one character at a time.
For each character, add it to the top of the stack.
Now, check if the top three characters in the stack form the sequence 'abc'.
If they do form 'abc', remove those three characters from the stack because they cancel each other out according to the rules.
If they don't form 'abc', just move on to the next character in the input string.
Keep doing this until you've processed the entire input string.
At the end, if the stack is empty, it means the entire input string was valid and could be reduced to nothing. Otherwise, it's not a valid string.

Code Implementation

def is_valid_after_substitutions(input_string):
    character_stack = []

    for character in input_string:
        character_stack.append(character)

        # Check for 'abc' sequence on top of stack.
        if len(character_stack) >= 3 and \
           character_stack[-3] == 'a' and \
           character_stack[-2] == 'b' and \
           character_stack[-1] == 'c':

            # Remove 'abc' from the stack.
            character_stack.pop()
            character_stack.pop()
            character_stack.pop()

    # If the stack is empty, the string is valid.
    return not character_stack

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return true if the string is null or empty because an empty string is considered valid after zero substitutions.
Input string is 'abc'	Return true because 'abc' represents a single 'abc' substitution.
Input string is 'ababcbc'	Return true; this is a valid sequence of substitutions.
Input string contains characters other than 'a', 'b', or 'c'	Return false immediately as these characters make it invalid per the problem definition.
Input string starts or ends with 'b' or 'c'	Return false immediately because the first 'abc' insertion always begins with 'a'.
Maximum input string size (considering potential stack overflow with recursion)	An iterative approach is required to handle large input strings and avoid stack overflow.
Input string contains uneven distribution of 'a', 'b', and 'c'	The algorithm should handle cases where the counts of 'a', 'b', and 'c' are not balanced, resulting in false.
Input string is 'abccba'	Return false; 'abc' can only be substituted if in sequence.