Jobs

Interviews

Discussions

Valid Parenthesis String

Medium

Amazon

3 views

Topics:

StringsTwo Pointers

Given a string s containing only three types of characters: (, ), and *, return true if s is valid.

The following rules define a valid string:

Any left parenthesis ( must have a corresponding right parenthesis ).
Any right parenthesis ) must have a corresponding left parenthesis (.
Left parentheses ( must go before the corresponding right parenthesis ).
* could be treated as a single right parenthesis ), a single left parenthesis (, or an empty string ``.

For example:

() is valid.
(*) is valid because the * can be a (.
(*)) is valid because the first * can be a (.
((*) is valid because the * can be a ).
) is invalid.
)( is invalid.

Write a function to determine if the input string is valid according to these rules. Explain the time and space complexity of your solution.

Valid Parenthesis String

Medium

Amazon

3 views

Topics:

StringsTwo Pointers

Given a string s containing only three types of characters: (, ), and *, return true if s is valid.

The following rules define a valid string:

Any left parenthesis ( must have a corresponding right parenthesis ).
Any right parenthesis ) must have a corresponding left parenthesis (.
Left parentheses ( must go before the corresponding right parenthesis ).
* could be treated as a single right parenthesis ), a single left parenthesis (, or an empty string ``.

For example:

() is valid.
(*) is valid because the * can be a (.
(*)) is valid because the first * can be a (.
((*) is valid because the * can be a ).
) is invalid.
)( is invalid.

Write a function to determine if the input string is valid according to these rules. Explain the time and space complexity of your solution.

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 `s` be null or empty?
Are there any constraints on the length of the input string `s`?
Besides '(', ')', and '*', can the input string contain any other characters?
If the string is invalid, should I return `false` immediately upon detection, or continue evaluating the entire string?
If multiple interpretations of '*' lead to a valid string, is that considered a valid string overall?

Brute Force Solution

Approach

The brute force approach to this parenthesis problem means we explore every single possible arrangement of the string. We will consider all the ways to treat asterisks as either open parenthesis, close parenthesis, or empty strings. Then, we'll check each arrangement to see if it's valid.

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

Consider the first asterisk in the string. We can treat it as an open parenthesis, a close parenthesis, or nothing at all. This creates three possibilities.
For each of those three possibilities, move to the next asterisk and again consider it as an open parenthesis, a close parenthesis, or nothing. This branches out the possibilities even further.
Keep repeating this process for every asterisk in the string. Each asterisk triples the number of possibilities we need to examine.
Once we have processed all asterisks and created a string containing only open and close parentheses, we check if it's a valid arrangement.
A valid arrangement means that for every close parenthesis, there is a matching open parenthesis before it, and we never have more close parentheses than open parentheses at any point.
Repeat the checking process for all possible arrangements of the string that we generated by treating asterisks in every possible way.
If at least one of these arrangements is valid, then the original string is considered a valid parenthesis string.

Code Implementation

def is_valid_parenthesis_string_brute_force(input_string):
    def check_valid(string_to_check):
        balance = 0
        for char in string_to_check:
            if char == '(': 
                balance += 1
            elif char == ')':
                balance -= 1
            if balance < 0:
                return False
        return balance == 0

    def generate_combinations(current_string, index):
        if index == len(input_string):
            #  If no more asterisks, check validity 
            if '*' not in current_string:
                return check_valid(current_string)
            else:
                return False

        if input_string[index] != '*':
            return generate_combinations(current_string + input_string[index], index + 1)
        else:
            # Explore all 3 possibilities for each asterisk 
            return (generate_combinations(current_string + '(', index + 1) or \
                    generate_combinations(current_string + ')', index + 1) or \
                    generate_combinations(current_string, index + 1))

    # Kick off the recursive process of exploring all combinations
    return generate_combinations('', 0)

Big(O) Analysis

Time Complexity

O(3^n) – The brute force approach considers all possible arrangements of the input string where each asterisk can be an open parenthesis, a close parenthesis, or an empty string. In the worst case, every character in the string is an asterisk. Therefore, for each asterisk, there are 3 choices. If the string has n characters that are all asterisks, the total number of possible strings to evaluate grows exponentially as 3*3*...*3 (n times), which is 3^n. Checking if each generated string is valid requires iterating through its characters, which is O(n), but this is dominated by the cost of generating the possible strings. Thus, the overall time complexity is O(3^n).

Space Complexity

O(3^N) – The brute force approach explores all possible arrangements of the string by treating each asterisk as an open parenthesis, a close parenthesis, or an empty string. In the worst case, where all characters are asterisks, each asterisk triples the number of possibilities. Thus, if there are N asterisks, the algorithm generates up to 3^N possible arrangements that could be stored. This exponential branching necessitates storing many intermediate string arrangements during the recursive exploration, leading to an auxiliary space usage of O(3^N), where N is the number of asterisks in the string. In the case where the number of asterisks is proportional to the length of the string we can generalize this as O(3^N) where N is the length of the string.

Optimal Solution

Approach

The key is to keep track of the possible range of open parentheses we could have at any point. We use two counters to track the minimum and maximum possible open parentheses, updating them as we go through the string. If the minimum ever goes negative, we know it's invalid.

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

Imagine you're tracking how many open parentheses you might have at any given point while reading the string.
Keep track of the smallest possible number of open parentheses and the largest possible number.
When you see an opening parenthesis, both your smallest and largest possible counts increase by one.
When you see a closing parenthesis, your smallest and largest counts both decrease by one.
When you see a star, the smallest possible count decreases by one, and the largest possible count increases by one.
If the largest possible number of open parentheses ever becomes negative, then there is no way to make the string valid, so we know it's invalid.
To make sure the string is valid, the smallest possible number of open parenthesis at the very end should be zero.
If the smallest possible number of open parenthesis is greater than zero, it means that we have unclosed open parentheses and the string is invalid.

Code Implementation

def is_valid_string(input_string: str) -> bool:
    minimum_open = 0
    maximum_open = 0

    for character in input_string:
        if character == '(': 
            minimum_open += 1
            maximum_open += 1

        elif character == ')':
            minimum_open -= 1
            maximum_open -= 1

        else:
            # Star can be ( or ) or empty
            minimum_open -= 1
            maximum_open += 1

        # If max open becomes negative, it is invalid
        if maximum_open < 0:
            return False

        # Minimum open can't be negative
        minimum_open = max(minimum_open, 0)

    # String is valid if min open is 0 at the end
    return minimum_open == 0

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string s of length n exactly once. Inside the loop, it performs a constant number of operations for each character, updating the min and max counts. Since the number of operations is directly proportional to the length of the string, the time complexity is O(n).

Space Complexity

O(1) – The algorithm uses two integer counters, representing the minimum and maximum open parentheses count, and these counters require constant space. The space used does not depend on the length of the input string, N. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty input string	Return true immediately as an empty string is considered valid.
String with only '*' characters	Return true since all '*' can be treated as empty strings.
String with only '(' characters	Return false as there are no corresponding ')' characters.
String with only ')' characters	Return false as there are no corresponding '(' characters.
String with many '(' at the beginning and many ')' at the end	The algorithm needs to efficiently handle deeply nested unbalanced parenthesis; the two-pass approach (left-to-right and right-to-left) correctly accounts for these unbalanced edge cases.
String with a high number of '*' characters interleaved with '(' and ')'	The algorithm considers all possible interpretations of '*' by maintaining low and high bounds, effectively pruning the search space of the exponential number of possibilities.
String like '()' where '' can balance the string	The low and high bounds will eventually both be zero at the end of iteration, resulting in true.
Very long input string (close to memory limit)	The space complexity of the algorithm is O(1), meaning the algorithm scales well with large inputs.

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 `s` be null or empty?
Are there any constraints on the length of the input string `s`?
Besides '(', ')', and '*', can the input string contain any other characters?
If the string is invalid, should I return `false` immediately upon detection, or continue evaluating the entire string?
If multiple interpretations of '*' lead to a valid string, is that considered a valid string overall?

Brute Force Solution

Approach

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

Consider the first asterisk in the string. We can treat it as an open parenthesis, a close parenthesis, or nothing at all. This creates three possibilities.
For each of those three possibilities, move to the next asterisk and again consider it as an open parenthesis, a close parenthesis, or nothing. This branches out the possibilities even further.
Keep repeating this process for every asterisk in the string. Each asterisk triples the number of possibilities we need to examine.
Once we have processed all asterisks and created a string containing only open and close parentheses, we check if it's a valid arrangement.
A valid arrangement means that for every close parenthesis, there is a matching open parenthesis before it, and we never have more close parentheses than open parentheses at any point.
Repeat the checking process for all possible arrangements of the string that we generated by treating asterisks in every possible way.
If at least one of these arrangements is valid, then the original string is considered a valid parenthesis string.

Code Implementation

def is_valid_parenthesis_string_brute_force(input_string):
    def check_valid(string_to_check):
        balance = 0
        for char in string_to_check:
            if char == '(': 
                balance += 1
            elif char == ')':
                balance -= 1
            if balance < 0:
                return False
        return balance == 0

    def generate_combinations(current_string, index):
        if index == len(input_string):
            #  If no more asterisks, check validity 
            if '*' not in current_string:
                return check_valid(current_string)
            else:
                return False

        if input_string[index] != '*':
            return generate_combinations(current_string + input_string[index], index + 1)
        else:
            # Explore all 3 possibilities for each asterisk 
            return (generate_combinations(current_string + '(', index + 1) or \
                    generate_combinations(current_string + ')', index + 1) or \
                    generate_combinations(current_string, index + 1))

    # Kick off the recursive process of exploring all combinations
    return generate_combinations('', 0)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine you're tracking how many open parentheses you might have at any given point while reading the string.
Keep track of the smallest possible number of open parentheses and the largest possible number.
When you see an opening parenthesis, both your smallest and largest possible counts increase by one.
When you see a closing parenthesis, your smallest and largest counts both decrease by one.
When you see a star, the smallest possible count decreases by one, and the largest possible count increases by one.
If the largest possible number of open parentheses ever becomes negative, then there is no way to make the string valid, so we know it's invalid.
To make sure the string is valid, the smallest possible number of open parenthesis at the very end should be zero.
If the smallest possible number of open parenthesis is greater than zero, it means that we have unclosed open parentheses and the string is invalid.

Code Implementation

def is_valid_string(input_string: str) -> bool:
    minimum_open = 0
    maximum_open = 0

    for character in input_string:
        if character == '(': 
            minimum_open += 1
            maximum_open += 1

        elif character == ')':
            minimum_open -= 1
            maximum_open -= 1

        else:
            # Star can be ( or ) or empty
            minimum_open -= 1
            maximum_open += 1

        # If max open becomes negative, it is invalid
        if maximum_open < 0:
            return False

        # Minimum open can't be negative
        minimum_open = max(minimum_open, 0)

    # String is valid if min open is 0 at the end
    return minimum_open == 0

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return true immediately as an empty string is considered valid.
String with only '*' characters	Return true since all '*' can be treated as empty strings.
String with only '(' characters	Return false as there are no corresponding ')' characters.
String with only ')' characters	Return false as there are no corresponding '(' characters.
String with many '(' at the beginning and many ')' at the end	The algorithm needs to efficiently handle deeply nested unbalanced parenthesis; the two-pass approach (left-to-right and right-to-left) correctly accounts for these unbalanced edge cases.
String with a high number of '*' characters interleaved with '(' and ')'	The algorithm considers all possible interpretations of '*' by maintaining low and high bounds, effectively pruning the search space of the exponential number of possibilities.
String like '()' where '' can balance the string	The low and high bounds will eventually both be zero at the end of iteration, resulting in true.
Very long input string (close to memory limit)	The space complexity of the algorithm is O(1), meaning the algorithm scales well with large inputs.