Valid Parenthesis String

Problem

A string of (, ), and is valid if you can replace every with (, ), or the empty string to produce a balanced parenthesis string. Return whether the input is valid.

Constraints

• 1 ≤ s.length ≤ 100
• s contains only (, ), and *.

Approach — Stack

This is a Stack problem. The idea: scan the input once, pushing work onto a stack and popping when the top can be resolved, so the stack always reflects what's still open. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time, O(n) space.

Solution code

Python

class Solution:
    def checkValidString(self, s):
        lo = hi = 0
        for c in s:
            if c == '(':
                lo += 1
                hi += 1
            elif c == ')':
                lo -= 1
                hi -= 1
            else:
                lo -= 1
                hi += 1
            if hi < 0:
                return False
            lo = max(lo, 0)
        return lo == 0

Java

import java.util.Stack;

class Solution {
    public boolean checkValidString(String s) {
        Stack<Integer> leftBrackets = new Stack<>();
        Stack<Integer> asterisks = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                leftBrackets.push(i);
            } else if (c == '*') {
                asterisks.push(i);
            } else {
                if (!leftBrackets.empty()) {
                    leftBrackets.pop();
                } else if (!asterisks.empty()) {
                    asterisks.pop();
                } else {
                    return false;
                }
            }
        }

        while (!leftBrackets.empty() && !asterisks.empty()) {
            if (leftBrackets.pop() > asterisks.pop()) {
                return false;
            }
        }

        return leftBrackets.empty();
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.