Valid Parenthesis String

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

Constraints

• 1 ≤ s.length ≤ 100
• s[i] is '(', ')' or '*'.

Greedy Balance Ranges

A standard parenthesis validator tracks the “balance” of open parentheses (increment on (, decrement on )). The balance must never drop below 0, and must end at exactly 0.

Because * can act as (, ), or "", the balance is not a single integer, but a range of possible balances [minOpen, maxOpen]:

• If we see (, both minOpen and maxOpen increment by 1.
• If we see ), both minOpen and maxOpen decrement by 1.
• If we see *:
  • It can act as ) (decrements minOpen) or ( (increments maxOpen). Thus: minOpen -= 1 and maxOpen += 1.

Rules:

1. Invalidity Check: If at any point maxOpen becomes negative, the string is invalid (we have too many ) characters, and even converting all * to ( cannot balance them). Return false.
2. Lower Bound Restraint: The balance of open parentheses cannot drop below 0. If minOpen becomes negative, reset minOpen = 0 (this means we greedily choose to treat some * as empty or ( instead of ) to prevent going negative).
3. End Condition: The string is valid if the range of possible balances at the end contains 0, which means minOpen == 0 at the end.

Solution: Range Tracking

class Solution {
    public boolean checkValidString(String s) {
        int minOpen = 0;
        int maxOpen = 0;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                minOpen++;
                maxOpen++;
            } else if (c == ')') {
                minOpen--;
                maxOpen--;
            } else { // c == '*'
                minOpen--;
                maxOpen++;
            }

            if (maxOpen < 0) return false;
            if (minOpen < 0) minOpen = 0; // reset lower bound
        }

        return minOpen == 0;
    }
}

class Solution:
    def checkValidString(self, s: str) -> bool:
        min_open = 0
        max_open = 0

        for char in s:
            if char == '(':
                min_open += 1
                max_open += 1
            elif char == ')':
                min_open -= 1
                max_open -= 1
            else:  # char == '*'
                min_open -= 1
                max_open += 1

            if max_open < 0:
                return False
            if min_open < 0:
                min_open = 0

        return min_open == 0

#include <string>
#include <algorithm>

class Solution {
public:
    bool checkValidString(std::string s) {
        int minOpen = 0;
        int maxOpen = 0;

        for (char c : s) {
            if (c == '(') {
                minOpen++;
                maxOpen++;
            } else if (c == ')') {
                minOpen--;
                maxOpen--;
            } else {
                minOpen--;
                maxOpen++;
            }

            if (maxOpen < 0) return false;
            if (minOpen < 0) minOpen = 0;
        }

        return minOpen == 0;
    }
};

Complexity Analysis:

• Time Complexity: O(N) where N is the length of the string s.
• Space Complexity: O(1) space.

← All Problems