921. Minimum Add to Make Parentheses Valid

Time: O(n)

Space: O(1)

Problem Overview

Every character that cannot be matched needs exactly one inserted partner, and every match that is possible should be taken.

Intuition

Every character that cannot be matched needs exactly one inserted partner, and every match that is possible should be taken. Scanning left to right, a closing parenthesis should pair with any opener still waiting, because leaving it unpaired only creates more work. If nothing is waiting, the closer can only be fixed by inserting an opener before it. Whatever openers are still waiting at the end each need a closer appended. A stack would hold exactly those unmatched characters, so two counters are enough.

Algorithm

1Start with open = 0 for waiting openers and adds = 0 for inserted openers.
2On an opening parenthesis, increase open.
3On a closing parenthesis, decrease open if it is positive. Otherwise increase adds.
4After the scan, return adds plus open.

Example Walkthrough

Input: s = "()))(("

1.The first pair matches, so open returns to 0.
2.The next two closers find nothing waiting, so adds becomes 2.
3.The last two openers are still waiting at the end, so open is 2.

Output: 4

Common Pitfalls

•Match a closer with a waiting opener whenever possible. Skipping a match never lowers the total.
•Openers left at the end also need partners, so add them to the answer.
•A closer that comes before any opener cannot be matched by an opener later in the string.
•A stack works but uses linear memory. The two counts carry everything it would store.

921.cs

// Approach: The stack only ever holds unmatched closers below unmatched
// openers, so two counters replace it. open counts openers still waiting for
// a match. A closer uses one of them if possible; otherwise it needs an added
// opener. The answer is those added openers plus the openers left at the end.
// Time: O(n) Space: O(1)

public class Solution
{
    public int MinAddToMakeValid(string s)
    {
        int open = 0;
        int adds = 0;
        foreach (char c in s)
        {
            if (c == '(')
                open++;
            else if (open > 0)
                open--;
            else
                adds++;
        }

        return adds + open;
    }
}

Was this solution helpful?