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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Valid Parenthesis String

Number: 678

Difficulty: Medium

Paid? No

Companies: Amazon, Meta, LinkedIn, TikTok, Microsoft, Apple, ServiceNow, Google, Bloomberg, Alibaba

Problem Description

Given a string s containing only three types of characters: '(', ')' and '*', determine if it can be considered valid. The validity is based on the following rules:

  1. Every '(' must have a corresponding ')'.
  2. Every ')' must have a corresponding '('.
  3. The '(' must come before its corresponding ')'.
  4. The '*' character can be treated as a '(' or ')' or an empty string.

Key Insights

  • The '*' character provides flexibility, allowing multiple interpretations.
  • A greedy approach can track the range of possible open parentheses count.
  • Use two counters to represent the minimum and maximum open count possible at any moment.
  • If the maximum count goes negative at any point, the string cannot be valid.
  • At the end, the minimum count must be zero for a valid string.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the string
Space Complexity: O(1)

Solution

We use a greedy algorithm by maintaining two counters:

  1. minOpen - the minimum number of open parentheses that could be present.
  2. maxOpen - the maximum number of open parentheses that could be present.

For every character in the string:

  • For '(', increment both minOpen and maxOpen.
  • For ')', decrement both minOpen and maxOpen.
  • For '*', decrement minOpen (treat as ')') and increment maxOpen (treat as '(').

Clamp minOpen to not go below 0, since negative count of open parentheses is not possible in any valid interpretation. If maxOpen drops below 0 at any point, it means there are more closing brackets than can be balanced by available '*' and '(', so the string is invalid. Finally, if minOpen is 0, the string can be balanced, otherwise it is invalid.

Code Solutions

# Python implementation with detailed inline comments

def checkValidString(s):
    # Initialize the minimum and maximum possible count of open parentheses
    minOpen = 0
    maxOpen = 0
    
    # Iterate over each character in the string
    for char in s:
        if char == '(':
            # For an open parenthesis, both min and max increase by 1
            minOpen += 1
            maxOpen += 1
        elif char == ')':
            # For a close parenthesis, both min and max decrease by 1
            minOpen -= 1
            maxOpen -= 1
        else:  # char == '*'
            # '*' can act as a ')' (decrease min) or '(' (increase max)
            minOpen -= 1
            maxOpen += 1
        
        # Ensure minOpen does not drop below 0
        if minOpen < 0:
            minOpen = 0
        
        # If maxOpen is negative, there are too many ')' to balance
        if maxOpen < 0:
            return False
    
    # The string is valid if there is a possible balance where minOpen equals 0
    return minOpen == 0

# Example usage:
print(checkValidString("(*)"))  # Expected output: True
← Back to All Questions