Minimum Add to Make Parentheses Valid

Medium
376.

Minimum Add to Make Parentheses Valid

Minimum Add to Make Parentheses Valid is a medium coding problem on strings, greedy and stack, asked in Amazon, Google and Meta interviews.

A parentheses string is valid if every open bracket has a matching close bracket in the right order.

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

Example 1

Input
s = "())"
Output
1

Example 2

Input
s = "((("
Output
3

Example 3

Input
s = "()"
Output
0

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 minAddToMakeValid = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Add to Make Parentheses Valid — Problem & Solution

Minimum Add to Make Parentheses Valid solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Minimum Add to Make Parentheses Valid is a medium coding problem on strings, greedy and stack, asked in Amazon, Google and Meta interviews.

  • Difficulty: Medium
  • Topics: Strings, Greedy, Stack
  • Asked at: Amazon, Google, Meta
  • 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

A parentheses string is valid if every open bracket has a matching close bracket in the right order.

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

Example 1

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

Example 2

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

Example 3

Input: s = "()"
Output: 0

Constraints

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

Hints for Minimum Add to Make Parentheses Valid

  1. Hint 1

    Sweep left to right keeping a count of unmatched open brackets.

  2. Hint 2

    A ) with no open bracket waiting can never be matched later, so it needs an insertion right away.

  3. Hint 3

    Whatever open brackets remain at the end each need a ) appended.

How to solve Minimum Add to Make Parentheses Valid

Count unmatched opens as you scan; a ) with none waiting needs an insertion immediately, and every open left at the end needs one too.

Approach

  1. For (, increment open; for ), decrement if open > 0, else increment needed.
  2. Return needed + open.

Why it works

An unmatched ) can only be fixed by a ( before it, and each leftover ( by a ) after it; the greedy match never wastes a bracket.

Complexity

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

Pitfalls

  • A stack is unnecessary — only its size matters.

Reference solution

Python

def minAddToMakeValid(s: str) -> int:
    open_count = 0
    needed = 0
    for ch in s:
        if ch == "(":
            open_count += 1
        elif open_count > 0:
            open_count -= 1
        else:
            needed += 1
    return needed + open_count

Java

public static int minAddToMakeValid(String s) {
    int open = 0, needed = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') open++;
        else if (open > 0) open--;
        else needed++;
    }
    return needed + open;
}

C++

int minAddToMakeValid(string s) {
    int open = 0, needed = 0;
    for (char c : s) {
        if (c == '(') open++;
        else if (open > 0) open--;
        else needed++;
    }
    return needed + open;
}

JavaScript

var minAddToMakeValid = function(s) {
    let open = 0, needed = 0;
    for (let i = 0; i < s.length; i++) {
        if (s.charAt(i) === "(") open++;
        else if (open > 0) open--;
        else needed++;
    }
    return needed + open;
};

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