Minimum Insertions to Balance a Parentheses String

Medium
405.

Minimum Insertions to Balance a Parentheses String

Minimum Insertions to Balance a Parentheses String is a medium coding problem on strings, greedy and stack, asked in Amazon and Google interviews.

In this problem a parentheses string is balanced when every '(' is matched by two consecutive '))', in that order.

Given a string s of '(' and ')', you may insert either bracket anywhere. Return the minimum number of insertions needed to make s balanced.

Example 1

Input
s = "(()))"
Output
1
Explanation
The inner "(" is closed by "))" but the outer one is one ")" short.

Example 2

Input
s = "())"
Output
0

Example 3

Input
s = "))())("
Output
3

Constraints

  • 1 <= s.length <= 40
  • s consists of '(' and ')'.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var minInsertions = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Insertions to Balance a Parentheses String Solution

Minimum Insertions to Balance a Parentheses String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Insertions to Balance a Parentheses String is a medium coding problem on strings, greedy and stack, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Strings, Greedy, Stack
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

In this problem a parentheses string is balanced when every '(' is matched by two consecutive '))', in that order.

Given a string s of '(' and ')', you may insert either bracket anywhere. Return the minimum number of insertions needed to make s balanced.

Example 1

Input: s = "(()))"
Output: 1
Explanation: The inner "(" is closed by "))" but the outer one is one ")" short.

Example 2

Input: s = "())"
Output: 0

Example 3

Input: s = "))())("
Output: 3

Constraints

  • 1 <= s.length <= 40
  • s consists of '(' and ')'.

Hints for Minimum Insertions to Balance a Parentheses String

  1. Hint 1

    Track need, the number of ) still owed. Each ( adds 2 to it.

  2. Hint 2

    If need ever turns odd when a ( arrives, the previous group was left with a single ) — insert one to square it up.

  3. Hint 3

    A ) with nothing owed needs a ( inserted before it; whatever is still owed at the end is inserted at the end.

How to solve Minimum Insertions to Balance a Parentheses String

Track need, the number of ) still owed. ( adds 2; if that makes need odd, a lone ) was left dangling — insert one. A ) with nothing owed needs a ( inserted before it.

Approach

  1. On (: need += 2; if need is odd, res += 1, need -= 1.
  2. On ): need -= 1; if need < 0, res += 1 and need = 1.
  3. Return res + need.

Why it works

Each ( must be followed by exactly two ); an odd need when a new ( starts means the previous group had a single ), which must be completed before the new group. A ) with no open group requires an inserted (, after which one more ) is still owed.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Whatever is owed at the end is appended, not forgotten.

Reference solution

Python

def minInsertions(s: str) -> int:
    res = 0
    need = 0
    for ch in s:
        if ch == "(":
            need += 2
            if need % 2 == 1:
                res += 1
                need -= 1
        else:
            need -= 1
            if need < 0:
                res += 1
                need = 1
    return res + need

Java

public static int minInsertions(String s) {
    int res = 0, need = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            need += 2;
            if (need % 2 == 1) {
                res++;
                need--;
            }
        } else {
            need--;
            if (need < 0) {
                res++;
                need = 1;
            }
        }
    }
    return res + need;
}

C++

int minInsertions(string s) {
    int res = 0, need = 0;
    for (char c : s) {
        if (c == '(') {
            need += 2;
            if (need % 2 == 1) {
                res++;
                need--;
            }
        } else {
            need--;
            if (need < 0) {
                res++;
                need = 1;
            }
        }
    }
    return res + need;
}

JavaScript

var minInsertions = function(s) {
    let res = 0;
    let need = 0;
    for (let i = 0; i < s.length; i++) {
        if (s.charAt(i) === "(") {
            need += 2;
            if (need % 2 === 1) {
                res++;
                need--;
            }
        } else {
            need--;
            if (need < 0) {
                res++;
                need = 1;
            }
        }
    }
    return res + need;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Greedy Algorithms