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

Valid Parenthesis String

Difficulty: Medium

Problem Description

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 ')', a single left parenthesis '(', or an empty string "".

Key Insights

  • Use a greedy approach to track the balance of parentheses.
  • Count the number of open parentheses and the maximum possible parentheses that can still be open due to '*'.
  • The '*' character adds flexibility in determining valid combinations.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To determine if the string is valid, we can use a greedy approach. We'll maintain two counters: one for the minimum number of open parentheses required and one for the maximum number that can be open at any point. As we iterate through the string:

  1. Increment the minimum counter when we encounter '('.
  2. Decrement the minimum counter when we encounter ')'.
  3. For '*', we can treat it as either '(', ')', or an empty string, so we increment the maximum counter and decrement the minimum counter.
  4. If the minimum counter drops below zero, it means there are too many closing parentheses and we cannot form a valid string, so we return false.
  5. At the end, if the maximum counter is zero or greater, the string is valid.

Code Solutions

def checkValidString(s: str) -> bool:
    min_open = 0  # Minimum number of open parentheses
    max_open = 0  # Maximum number of open parentheses

    for char in s:
        if char == '(':
            min_open += 1  # We have one more open parenthesis
            max_open += 1  # We can potentially have one more open parenthesis
        elif char == ')':
            min_open -= 1  # We close one parenthesis
            max_open -= 1  # We could potentially close one parenthesis
        else:  # char == '*'
            min_open -= 1  # '*' can be treated as ')'
            max_open += 1  # '*' can also be treated as '('

        if max_open < 0:  # Too many closing parentheses
            return False
        min_open = max(min_open, 0)  # We can't have negative open parentheses

    return min_open == 0  # All opened must be closed
← Back to All Questions