Problem

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

Solution

This is more of a dp solution, but greedy algorithm is simple, but it is hard to come up with.

Method 1 - Greedy

Note

  • Open parenthesis ( shouldn’t be less than closing parenthesis ')' at any time.
  • If there are too many ')', return false immediately. If there are no unmatched ')' at the end, the string is valid.

Explanation

We count the number of closing parenthesis ')' we are waiting for, and it’s equal to the number of open parenthesis. This number will be in a range and we count it as [cmin, cmax], where:

  • cmax tracks the maximum number of unbalanced '(' that could be paired.
  • cmin tracks the minimum number of unmatched '(' that must be paired.

Example

It’s quite straight forward actually. When you encounter '(', you know you need one only one ')', cmin = 1 and cmax = 1. When you encounter '(' you know you need one/two/three ')', cmin = 1 and cmax = 3.

The string is valid for 2 condition:

  1. cmax will never be negative.
  2. cmin is 0 at the end.

Time Complexity:

One pass O(N) time, Space O(1)

Code

Java
class Solution {
    public boolean checkValidString(String s) {
        int cmin = 0, cmax = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                cmax++;
                cmin++;
            } else if (c == ')') {
                cmax--;
                cmin = Math.max(cmin - 1, 0);
            } else {
                cmax++;
                cmin = Math.max(cmin - 1, 0);
            }
            if (cmax < 0) return false;
        }
        return cmin == 0;
    }
}
Python
class Solution:
    def checkValidString(self, s: str) -> bool:
        cmin = 0
        cmax = 0
        for ch in s:
            if ch == '(':
                cmax += 1
                cmin += 1
            elif ch == ')':
                cmax -= 1
                cmin = max(cmin - 1, 0)
            else:
                cmax += 1
                cmin = max(cmin - 1, 0)
            if cmax < 0:
                return False
        return cmin == 0

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)