LeetCode 678: Valid Parenthesis String

Problem Description

LeetCode Problem 678

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 ’*‘.

Difficulty: Medium

Tags: string, dynamic programming, stack, greedy

Rating: 97.01%

Solution

Here’s my Python solution to this problem:

class Solution:
    def checkValidString(self, s: str) -> bool:
        min_open = max_open = 0
        
        for c in s:
            if c == "(":
                min_open += 1
                max_open += 1
            elif c == ")":
                min_open -= 1
                max_open -= 1
            else:  # c == '*'
                min_open -= 1  # treat as ')'
                max_open += 1  # treat as '('
            
            # If max becomes negative, we have too many ')'
            if max_open < 0: 
                return False
                
            # min_open can't be negative
            min_open = max(0, min_open)
            
        return min_open == 0  # possible to have no open parentheses

Example Walkthrough

Let’s walk through the example "(*)" step by step:

1. Initial state: min_open = 0, max_open = 0

2. Process '(':

   • min_open = 1 (must be treated as open parenthesis)
   • max_open = 1 (must be treated as open parenthesis)

   ( → min_open = 1, max_open = 1
   

3. Process '*':

   • min_open = 0 (could be treated as closing parenthesis)
   • max_open = 2 (could be treated as opening parenthesis)

   (* → min_open = 0, max_open = 2
   

4. Process ')':

   • min_open = -1 → adjusted to 0 (minimum can’t be negative)
   • max_open = 1

   (*) → min_open = 0, max_open = 1
   

5. Final check: min_open == 0 is true, so return true

Why This Works

The solution works because:

1. If max_open becomes negative, we have too many ) and no valid solution exists
2. If min_open is 0 at the end, there exists at least one way to assign * characters to make the string valid
3. By keeping track of both minimum and maximum possible open parentheses, we cover all possible combinations of * interpretations

Complexity Analysis

• Time Complexity: $O(n)$ where n is the length of the string
• Space Complexity: $O(1)$ as we only use two variables regardless of input size