DDSA Solutions

1541. Minimum Insertions to Balance a Parentheses String

MediumView on LeetCode
StringStackGreedy
Time: O(n)
Space: O(1)

Problem Overview

Here every opening parenthesis must be closed by two consecutive closing parentheses.

Intuition

Here every opening parenthesis must be closed by two consecutive closing parentheses. Scanning left to right, it is enough to track how many closers are still owed. Two situations force an insertion. A closer that arrives when nothing is owed needs an inserted opener in front of it. An opener that arrives while an odd number of closers is owed means one closer was left alone, so a closer must be inserted to finish that pair. Whatever is still owed at the end must be appended.

Algorithm

  1. 1Keep the number of closers owed, the inserted openers, and the inserted closers.
  2. 2On an opener, if an odd number of closers is owed, insert one closer and lower the owed count by one. Then add two to the owed count.
  3. 3On a closer, lower the owed count. If it drops below zero, insert an opener and add two back.
  4. 4Return the owed count plus both insertion counts.

Example Walkthrough

Input: s = "(()))"

  1. 1.The two openers make four closers owed.
  2. 2.The three closers lower that to one.
  3. 3.One closer is still owed at the end, so one insertion finishes the string.

Output: 1

Common Pitfalls

  • •The two closers for one opener must be next to each other. A lone closer followed by an opener needs a fix right there.
  • •A closer with nothing owed needs an inserted opener, and that opener still owes one more closer.
  • •Do not forget the closers still owed at the end of the scan.
  • •A stack works but uses linear memory. Three counters carry everything it would store.
1541.cs
C#
// Approach: Each '(' needs two consecutive ')'. Track how many closers are
// still owed. A new '(' arriving while an odd number is owed means a single
// ')' was left alone, so one ')' is inserted to finish that pair. A ')' with
// nothing owed needs an inserted '(' and leaves one more ')' owed. The
// answer is the inserted characters plus whatever is still owed at the end.
// Time: O(n) Space: O(1)

public class Solution
{
    public int MinInsertions(string s)
    {
        int neededRight = 0;  // Increment by 2 for each '('.
        int missingLeft = 0;  // Increment by 1 for each missing '('.
        int missingRight = 0; // Increment by 1 for each missing ')'.

        foreach (char c in s)
        {
            if (c == '(')
            {
                if (neededRight % 2 == 1)
                {
                    // e.g. "()(..."
                    ++missingRight;
                    --neededRight;
                }
                neededRight += 2;
            }
            else if (--neededRight < 0)
            { // c == ')'
                // e.g. "()))..."
                ++missingLeft;
                neededRight += 2;
            }
        }

        return neededRight + missingLeft + missingRight;
    }
}
Was this solution helpful?

Related Problems