678. Valid Parenthesis String

MediumView on LeetCode

String Dynamic Programming Stack Greedy

Time: O(n)

Space: O(1)

Problem Overview

A star can act as an opening parenthesis, a closing one, or nothing.

Intuition

A star can act as an opening parenthesis, a closing one, or nothing. Two failures are possible: a closing parenthesis with nothing able to open it, or an opening parenthesis with nothing able to close it. Reading left to right and treating every star as an opener is the most generous way to cover closers, so if that count still goes negative, no choice of stars helps. Reading right to left and treating every star as a closer checks the openers the same way. If neither count ever goes negative, the stars can be assigned to balance the string.

Algorithm

1Keep two counters and walk index i from 0 to n minus 1.
2The forward counter reads s[i]. Add one for an opening parenthesis or a star, and subtract one for a closing parenthesis.
3The backward counter reads s[n minus 1 minus i]. Add one for a closing parenthesis or a star, and subtract one for an opening parenthesis.
4If either counter drops below zero, return false right away.
5If the loop finishes, return true.

Example Walkthrough

Input: s = "(*))"

1.Forward, the counter goes 1, 2, 1, 0 because the star counts as an opener. It never goes negative.
2.Backward, it reads ), ), *, ( and goes 1, 2, 3, 2. It never goes negative either.
3.The star can act as an opener, giving (()), so the string is valid.

Output: true

Common Pitfalls

•One pass is not enough. "((*" passes the forward check, but the backward check fails because the second opener has nothing to close it.
•A star may also be empty. The two checks cover that, because a star that is not needed in either direction can be dropped.
•Stop as soon as a counter is negative. Later characters cannot repair an unmatched prefix.
•The low and high open count method is another linear, constant memory solution with the same cost.

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?