Minimum Remove to Make Valid Parentheses

Medium
377.

Minimum Remove to Make Valid Parentheses

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

Given a string s of lowercase letters and parentheses, remove the minimum number of parentheses so that the result is valid.

A string is valid if the brackets match and the letters are left untouched. If several answers have the same minimal length, any of them is accepted; return the one produced by removing unmatched brackets and keeping everything else in place.

Example 1

Input
s = "lee(t(c)o)de)"
Output
lee(t(c)o)de
Explanation
The last ')' has no partner.

Example 2

Input
s = "a)b(c)d"
Output
ab(c)d

Example 3

Input
s = "))(("
Output

Constraints

  • 1 <= s.length <= 40
  • s consists of lowercase English letters, '(' 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 {string}
 */
var minRemoveToMakeValid = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Remove to Make Valid Parentheses — Solution

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

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

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

Given a string s of lowercase letters and parentheses, remove the minimum number of parentheses so that the result is valid.

A string is valid if the brackets match and the letters are left untouched. If several answers have the same minimal length, any of them is accepted; return the one produced by removing unmatched brackets and keeping everything else in place.

Example 1

Input: s = "lee(t(c)o)de)"
Output: lee(t(c)o)de
Explanation: The last ')' has no partner.

Example 2

Input: s = "a)b(c)d"
Output: ab(c)d

Example 3

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

Constraints

  • 1 <= s.length <= 40
  • s consists of lowercase English letters, '(' and ')'.

Hints for Minimum Remove to Make Valid Parentheses

  1. Hint 1

    Do one pass keeping a stack of the indices of unmatched (.

  2. Hint 2

    A ) with an empty stack is unmatched — mark it for deletion immediately.

  3. Hint 3

    Whatever indices remain on the stack at the end are unmatched ( — mark those too, then rebuild the string.

How to solve Minimum Remove to Make Valid Parentheses

One pass with a stack of unmatched ( indices: a ) with an empty stack is marked for removal on the spot, and every index left on the stack is removed at the end.

Approach

  1. Walk the string; push indices of (, pop on ) when possible, else mark the ).
  2. Mark every index remaining on the stack.
  3. Rebuild the string from the unmarked characters.

Why it works

The greedy matching pairs each ) with the nearest available (; the brackets left unmatched are exactly the minimum set whose removal balances the string.

Complexity

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

Pitfalls

  • Letters are never removed; only the marked brackets are dropped.

Reference solution

Python

def minRemoveToMakeValid(s: str) -> str:
    keep = [True] * len(s)
    open_idx = []
    for i, ch in enumerate(s):
        if ch == "(":
            open_idx.append(i)
        elif ch == ")":
            if open_idx:
                open_idx.pop()
            else:
                keep[i] = False
    for i in open_idx:
        keep[i] = False
    return "".join(ch for ch, k in zip(s, keep) if k)

Java

public static String minRemoveToMakeValid(String s) {
    boolean[] keep = new boolean[s.length()];
    Arrays.fill(keep, true);
    Deque<Integer> openIdx = new ArrayDeque<>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '(') {
            openIdx.push(i);
        } else if (c == ')') {
            if (!openIdx.isEmpty()) openIdx.pop();
            else keep[i] = false;
        }
    }
    for (int i : openIdx) keep[i] = false;
    StringBuilder out = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        if (keep[i]) out.append(s.charAt(i));
    }
    return out.toString();
}

C++

string minRemoveToMakeValid(string s) {
    vector<bool> keep(s.size(), true);
    vector<int> openIdx;
    for (int i = 0; i < (int) s.size(); i++) {
        if (s[i] == '(') openIdx.push_back(i);
        else if (s[i] == ')') {
            if (!openIdx.empty()) openIdx.pop_back();
            else keep[i] = false;
        }
    }
    for (int i : openIdx) keep[i] = false;
    string out;
    for (int i = 0; i < (int) s.size(); i++) {
        if (keep[i]) out.push_back(s[i]);
    }
    return out;
}

JavaScript

var minRemoveToMakeValid = function(s) {
    const keep = [];
    for (let i = 0; i < s.length; i++) keep.push(true);
    const openIdx = [];
    for (let i = 0; i < s.length; i++) {
        const c = s.charAt(i);
        if (c === "(") openIdx.push(i);
        else if (c === ")") {
            if (openIdx.length > 0) openIdx.pop();
            else keep[i] = false;
        }
    }
    for (let i = 0; i < openIdx.length; i++) keep[openIdx[i]] = false;
    let out = "";
    for (let i = 0; i < s.length; i++) {
        if (keep[i]) out += s.charAt(i);
    }
    return out;
};

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 · Stack Data Structure