Jobs

Interviews

Discussions

Valid Parenthesis String

Medium

Asked by:

24 views

Topics:

ArraysTwo PointersGreedy Algorithms

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 parenthesis '(' must go before the corresponding right parenthesis ')'.
'*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string "".

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "(*)"
Output: true

Example 3:

Input: s = "(*))"
Output: true

Constraints:

1 <= s.length <= 100
s[i] is '(', ')' or '*'.

Valid Parenthesis String

Medium

Asked by:

24 views

Topics:

ArraysTwo PointersGreedy Algorithms

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 parenthesis '(' must go before the corresponding right parenthesis ')'.
'*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string "".

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "(*)"
Output: true

Example 3:

Input: s = "(*))"
Output: true

Constraints:

1 <= s.length <= 100
s[i] is '(', ')' or '*'.

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:

What is the maximum length of the input string `s`?
Can the input string `s` be empty or null?
If the string is invalid, should I return `false` immediately upon detection, or should I continue processing the entire string to ensure there aren't other ways the string could be valid using the '*' character?
Are there any memory constraints I should be aware of, given the potential length of the string?
Are there any specific criteria for determining validity beyond the rules you've already stated, such as a minimum number of '*' characters that must be used as '(' or ')'?

Brute Force Solution

Approach

The brute force approach to this parenthesis problem involves exploring every possible combination of open, close, or wildcard characters. We treat each wildcard as either an open or a close parenthesis and try all combinations. Then, we check if each combination results in a 'valid' arrangement of parentheses.

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

Consider each wildcard character one by one.
For each wildcard, imagine it could be an open parenthesis or a closed parenthesis.
Replace each wildcard with an open parenthesis, creating one possible string.
Replace the same wildcard with a closed parenthesis, creating another possible string.
Repeat this process for every wildcard in the original string; each wildcard will double the number of possible strings.
Once all wildcards have been replaced, we have a large collection of strings with only open and close parentheses.
Go through each of these strings and check if the parentheses are correctly balanced (each open has a matching close in the correct order).
If any of the fully-formed strings are balanced, the original string is considered valid.

Code Implementation

def valid_parenthesis_string_brute_force(input_string):

    possible_strings = []
    
    def generate_combinations(current_string, index):
        if index == len(input_string):
            possible_strings.append(current_string)
            return

        if input_string[index] == '*':
            # Try replacing '*' with '(' 
            generate_combinations(current_string + '(', index + 1)

            # Try replacing '*' with ')'
            generate_combinations(current_string + ')', index + 1)
        else:
            generate_combinations(current_string + input_string[index], index + 1)

    generate_combinations("", 0)

    def is_valid(check_string):
        balance = 0
        for char in check_string:
            if char == '(': 
                balance += 1
            elif char == ')':
                balance -= 1
            if balance < 0:
                return False
        return balance == 0

    # Check if ANY of the generated strings are valid
    for possible_string in possible_strings:
        if is_valid(possible_string):
            return True

    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^n) – The algorithm explores all possible combinations of open and close parentheses for each wildcard character. If there are 'n' wildcard characters in the string, each wildcard can be either an open or close parenthesis, leading to 2^n possible combinations. For each of these 2^n combinations, we iterate through the string of length n to validate if the parentheses are balanced. Therefore, the overall time complexity is O(n * 2^n), which simplifies to O(2^n) since 2^n grows faster than n.

Space Complexity

O(2^N) – The brute force approach generates all possible combinations of replacing each wildcard character with either an open or closed parenthesis. If there are N wildcard characters in the input string, it will generate 2^N possible strings. These strings are stored in memory to check for validity, resulting in auxiliary space proportional to 2 raised to the power of the number of wildcards. Therefore, the space complexity is O(2^N), where N is the number of wildcard characters.

Optimal Solution

Approach

The key idea is to keep track of the possible balance of opening and closing parenthesis. We consider how many unmatched open parenthesis we *could* have, and how few we *must* have, after reading each character. If the range between those two values ever becomes invalid, we know the string is invalid.

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

Keep track of the minimum number of open parenthesis we need to balance what we've seen so far. Call this our 'low' count.
Also keep track of the maximum number of open parenthesis we could have, considering '*' can be an open parenthesis. Call this our 'high' count.
Start reading the string from left to right, character by character.
If we see an open parenthesis, increase both 'low' and 'high' counts.
If we see a closing parenthesis, decrease both 'low' and 'high' counts.
If we see a '*', we can treat it as either an open, a close, or nothing. So, increase 'high' and decrease 'low'.
If 'high' ever goes negative, it means we have too many closing parenthesis and the string is invalid. We can stop and return that it is invalid.
After each character, make sure 'low' never goes below zero. If it does, set it back to zero, because any extra closing parenthesis before this point don't affect the overall validity.
After processing the entire string, the string is valid if 'low' is zero. Meaning all open parenthesis have been matched by either closing parenthesis or '*'.

Code Implementation

def is_valid_parenthesis_string(input_string):
    minimum_open_count = 0
    maximum_open_count = 0

    for character in input_string:
        if character == '(': 
            minimum_open_count += 1
            maximum_open_count += 1
        elif character == ')':
            minimum_open_count -= 1
            maximum_open_count -= 1
        else:
            minimum_open_count -= 1
            maximum_open_count += 1

        # Too many closing parenthesis, invalid
        if maximum_open_count < 0:
            return False

        # Resetting to zero, since negatives don't matter
        minimum_open_count = max(minimum_open_count, 0)

    # String is valid if all open parenthesis are matched
    return minimum_open_count == 0

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string once, character by character, to update the low and high counts. The number of operations performed for each character is constant (incrementing/decrementing counters and comparing values). Since the number of operations scales linearly with the length of the input string (n), the time complexity is O(n).

Space Complexity

O(1) – The algorithm uses only two integer variables, 'low' and 'high', to keep track of the minimum and maximum possible open parenthesis count. The space used by these variables remains constant regardless of the input string's length, N. No auxiliary data structures like arrays, lists, or hash maps are created. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty string input	Return true immediately because an empty string is considered valid.
String containing only '*'	Return true because '*' can be treated as an empty string, resulting in a valid string.
String containing only '('	Return false because there are unmatched opening parentheses.
String containing only ')'	Return false because there are unmatched closing parentheses.
String with deeply nested '(' before any ')' or '*'	The solution needs to ensure that the available '*' characters can balance these deep nestings.
String with many ')' at the beginning before any '(' or '*'	The solution should handle the case where right parentheses appear before left parentheses with the help of '*'.
String with a large number of '*' characters interspersed among '(' and ')'	The solution should explore all possibilities of '*' which may lead to potential time complexity issues and should be handled carefully.
Very long input string to check for performance	An efficient algorithm with linear time complexity, like using a balance counter or dynamic programming with memoization, is necessary to avoid timeouts.

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:

What is the maximum length of the input string `s`?
Can the input string `s` be empty or null?
If the string is invalid, should I return `false` immediately upon detection, or should I continue processing the entire string to ensure there aren't other ways the string could be valid using the '*' character?
Are there any memory constraints I should be aware of, given the potential length of the string?
Are there any specific criteria for determining validity beyond the rules you've already stated, such as a minimum number of '*' characters that must be used as '(' or ')'?

Brute Force Solution

Approach

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

Consider each wildcard character one by one.
For each wildcard, imagine it could be an open parenthesis or a closed parenthesis.
Replace each wildcard with an open parenthesis, creating one possible string.
Replace the same wildcard with a closed parenthesis, creating another possible string.
Repeat this process for every wildcard in the original string; each wildcard will double the number of possible strings.
Once all wildcards have been replaced, we have a large collection of strings with only open and close parentheses.
Go through each of these strings and check if the parentheses are correctly balanced (each open has a matching close in the correct order).
If any of the fully-formed strings are balanced, the original string is considered valid.

Code Implementation

def valid_parenthesis_string_brute_force(input_string):

    possible_strings = []
    
    def generate_combinations(current_string, index):
        if index == len(input_string):
            possible_strings.append(current_string)
            return

        if input_string[index] == '*':
            # Try replacing '*' with '(' 
            generate_combinations(current_string + '(', index + 1)

            # Try replacing '*' with ')'
            generate_combinations(current_string + ')', index + 1)
        else:
            generate_combinations(current_string + input_string[index], index + 1)

    generate_combinations("", 0)

    def is_valid(check_string):
        balance = 0
        for char in check_string:
            if char == '(': 
                balance += 1
            elif char == ')':
                balance -= 1
            if balance < 0:
                return False
        return balance == 0

    # Check if ANY of the generated strings are valid
    for possible_string in possible_strings:
        if is_valid(possible_string):
            return True

    return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Keep track of the minimum number of open parenthesis we need to balance what we've seen so far. Call this our 'low' count.
Also keep track of the maximum number of open parenthesis we could have, considering '*' can be an open parenthesis. Call this our 'high' count.
Start reading the string from left to right, character by character.
If we see an open parenthesis, increase both 'low' and 'high' counts.
If we see a closing parenthesis, decrease both 'low' and 'high' counts.
If we see a '*', we can treat it as either an open, a close, or nothing. So, increase 'high' and decrease 'low'.
If 'high' ever goes negative, it means we have too many closing parenthesis and the string is invalid. We can stop and return that it is invalid.
After each character, make sure 'low' never goes below zero. If it does, set it back to zero, because any extra closing parenthesis before this point don't affect the overall validity.
After processing the entire string, the string is valid if 'low' is zero. Meaning all open parenthesis have been matched by either closing parenthesis or '*'.

Code Implementation

def is_valid_parenthesis_string(input_string):
    minimum_open_count = 0
    maximum_open_count = 0

    for character in input_string:
        if character == '(': 
            minimum_open_count += 1
            maximum_open_count += 1
        elif character == ')':
            minimum_open_count -= 1
            maximum_open_count -= 1
        else:
            minimum_open_count -= 1
            maximum_open_count += 1

        # Too many closing parenthesis, invalid
        if maximum_open_count < 0:
            return False

        # Resetting to zero, since negatives don't matter
        minimum_open_count = max(minimum_open_count, 0)

    # String is valid if all open parenthesis are matched
    return minimum_open_count == 0

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty string input	Return true immediately because an empty string is considered valid.
String containing only '*'	Return true because '*' can be treated as an empty string, resulting in a valid string.
String containing only '('	Return false because there are unmatched opening parentheses.
String containing only ')'	Return false because there are unmatched closing parentheses.
String with deeply nested '(' before any ')' or '*'	The solution needs to ensure that the available '*' characters can balance these deep nestings.
String with many ')' at the beginning before any '(' or '*'	The solution should handle the case where right parentheses appear before left parentheses with the help of '*'.
String with a large number of '*' characters interspersed among '(' and ')'	The solution should explore all possibilities of '*' which may lead to potential time complexity issues and should be handled carefully.
Very long input string to check for performance	An efficient algorithm with linear time complexity, like using a balance counter or dynamic programming with memoization, is necessary to avoid timeouts.