678. Valid Parenthesis String

Jump to Solution: Python Java C++ JavaScript C#

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

Examples:

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 '*'.

Python Solution

class Solution:
    def checkValidString(self, s: str) -> bool:
        min_open = max_open = 0
        
        for char in s:
            if char == '(':
                min_open += 1
                max_open += 1
            elif char == ')':
                min_open = max(0, min_open - 1)
                max_open -= 1
                if max_open < 0:
                    return False
            else:  # char == '*'
                min_open = max(0, min_open - 1)
                max_open += 1
                
        return min_open == 0

Alternative Solution (Using Stack):

class Solution:
    def checkValidString(self, s: str) -> bool:
        left_stack = []
        star_stack = []
        
        for i, char in enumerate(s):
            if char == '(':
                left_stack.append(i)
            elif char == '*':
                star_stack.append(i)
            else:  # char == ')'
                if left_stack:
                    left_stack.pop()
                elif star_stack:
                    star_stack.pop()
                else:
                    return False
                    
        while left_stack and star_stack:
            if left_stack[-1] > star_stack[-1]:
                return False
            left_stack.pop()
            star_stack.pop()
            
        return len(left_stack) == 0

Implementation Notes:

First solution uses min/max open parentheses count
Second solution uses two stacks for tracking
Time complexity: O(n) for both solutions
Space complexity: O(1) for first solution, O(n) for second

Java Solution

class Solution {
    public boolean checkValidString(String s) {
        int minOpen = 0, maxOpen = 0;
        
        for (char c : s.toCharArray()) {
            if (c == '(') {
                minOpen++;
                maxOpen++;
            } else if (c == ')') {
                minOpen = Math.max(0, minOpen - 1);
                maxOpen--;
                if (maxOpen < 0) {
                    return false;
                }
            } else {  // c == '*'
                minOpen = Math.max(0, minOpen - 1);
                maxOpen++;
            }
        }
        
        return minOpen == 0;
    }
}

C++ Solution

class Solution {
public:
    bool checkValidString(string s) {
        int minOpen = 0, maxOpen = 0;
        
        for (char c : s) {
            if (c == '(') {
                minOpen++;
                maxOpen++;
            } else if (c == ')') {
                minOpen = max(0, minOpen - 1);
                maxOpen--;
                if (maxOpen < 0) {
                    return false;
                }
            } else {  // c == '*'
                minOpen = max(0, minOpen - 1);
                maxOpen++;
            }
        }
        
        return minOpen == 0;
    }
};

JavaScript Solution

/**
 * @param {string} s
 * @return {boolean}
 */
var checkValidString = function(s) {
    let minOpen = 0, maxOpen = 0;
    
    for (const c of s) {
        if (c === '(') {
            minOpen++;
            maxOpen++;
        } else if (c === ')') {
            minOpen = Math.max(0, minOpen - 1);
            maxOpen--;
            if (maxOpen < 0) {
                return false;
            }
        } else {  // c === '*'
            minOpen = Math.max(0, minOpen - 1);
            maxOpen++;
        }
    }
    
    return minOpen === 0;
};

C# Solution

public class Solution {
    public bool CheckValidString(string s) {
        int minOpen = 0, maxOpen = 0;
        
        foreach (char c in s) {
            if (c == '(') {
                minOpen++;
                maxOpen++;
            } else if (c == ')') {
                minOpen = Math.Max(0, minOpen - 1);
                maxOpen--;
                if (maxOpen < 0) {
                    return false;
                }
            } else {  // c == '*'
                minOpen = Math.Max(0, minOpen - 1);
                maxOpen++;
            }
        }
        
        return minOpen == 0;
    }
}

Implementation Notes:

Uses min/max open parentheses count approach
Time complexity: O(n)
Space complexity: O(1)
Handles all possible cases for wildcard character