678. Valid Parenthesis String

Time: O(n)

Space: O(1)

Intuition

Track the range [lo, hi] of possible open bracket counts. '(' increases both, ')' decreases both, '*' expands range. If hi<0 at any point, invalid. Return lo==0 at end.

Algorithm

1lo=0, hi=0.
2For each char: if '(': lo++,hi++. If ')': lo--,hi--. If '*': lo--,hi++.
3lo = max(lo, 0) (can't have negative open count).
4If hi < 0: return false.
5Return lo == 0.

Example Walkthrough

Input: "(*)"

1.(: lo=1,hi=1. *: lo=0,hi=2. ): lo=-1→0, hi=1. End lo=0 ✓.

Output: true

Common Pitfalls

•Clamp lo to 0 after each step. If hi goes negative, it's impossible.

678.cs

// Approach: Two-pass greedy — treat '*' as '(' left-to-right and as ')'
// right-to-left; fail if either running count goes negative.
// Time: O(n) Space: O(1)

public class Solution
{
    public bool CheckValidString(string s)
    {
        int oc = 0, cc = 0;
        int n = s.Length;

        for (int i = 0; i < n; i++)
        {
            if (s[i] == '(' || s[i] == '*')
                oc++;
            else
                oc--;

            if (s[n - 1 - i] == ')' || s[n - 1 - i] == '*')
                cc++;
            else
                cc--;

            if (oc < 0 || cc < 0)
                return false;
        }

        return true;
    }
}

Was this solution helpful?