Skip to content

1249. Minimum Remove to Make Valid Parentheses

Solve in Leetcode

Description

Static Badge

Given a string s of '(' , ')' and lowercase English characters.

Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

  • It is the empty string, contains only lowercase characters, or
  • It can be written as AB (A concatenated with B), where A and B are valid strings, or
  • It can be written as (A), where A is a valid string.

Example 1

  • Input: s = "lee(t(c)o)de)"
  • Output: "lee(t(c)o)de"
  • Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.

Example 2

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

Example 3

  • Input: s = "))(("
  • Output: ""
  • Explanation: An empty string is also valid.

Constraints

  • 1 <= s.length <= 105
  • s[i] is either'(' , ')', or lowercase English letter.

Solution 1: Stack1 with character index

  • We use a stack to store the index of the opening parenthesis ( from s.
  • When we encounter a closing parenthesis ), we pop the index from the stack if there's an open parenthesis to be paired. Otherwise, we will remove the closing parenthesis ) from the s.
  • After that, we will iterate through stack and remove all the non-matching opening parenthesis ( from the s.
Time Complexity O(n)

  1. Convert string s to array chars to make it mutable

    • This loop iterates through each character in the input string s, which has n characters.
    • Time complexity: O(n), where n is the length of the input string s.

  2. Using a stack brackets to track open brackets' indices

    • Pushing and popping elements from an array brackets takes O(1) time complexity on average.
    • In the worst case, each character could be an opening bracket, leading to n operations of pushing or popping.
    • Time complexity: O(n), where n is the length of the input string s.

  3. Iterating through the stack brackets to remove remaining open brackets

    • This loop iterates through the remaining indices in the brackets array.
    • Time complexity: O(m), where m is the number of remaining open brackets.

Overall, the time complexity of the function is O(n + m), where n is the length of the input string s, and m is the number of remaining open brackets in stack after balancing the parentheses.

Space Complexity O(n)

  1. Create an array chars to store the characters of the input string s.

    • The space required is proportional to the length of the input string s.
    • Space complexity: O(n), where n is the length of the input string s.

  2. Using a stack brackets to track open brackets' indices

    • The space required for the stack is proportional to the number of open brackets.
    • In the worst case, all opening brackets are pushed onto the stack.
    • Space complexity: O(m), where m is the number of open brackets in the input string s.

  3. Additional space for the brackets array

    • This array stores indices of opening brackets temporarily until they are balanced.
    • Space complexity: O(m), where m is the number of open brackets in the input string s.

Overall, the space complexity of the function is O(n + m), where n is the length of the input string s, and m is the number of open brackets in the input string s.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
function minRemoveToMakeValid(s: string): string {
    let chars = Array.from(s);
    let brackets: Array<number> = [];

    for (var i: number = 0; i < chars.length; i++) {
        // Get maximum full brackets can accepted
        if (chars[i] == "(") brackets.push(i);
        else if (chars[i] == ")") {
            // comsume one brackets index if full bracket
            if (brackets.length > 0) brackets.pop();
            // remove if no open bracket
            else chars[i] = ""
        }
    }

    // Convert remaining unuse open brackets to empty string in [s] based on stored indexes
    for (var i = 0; i < brackets.length; i++) {
        chars[brackets[i]] = "";
    }

    return chars.join("");
};

2Solution 2: Counting Open and Close Parentheses without Stack

  • We can solve this problem without using a stack by counting the number of open and close parentheses.
  • We will iterate through the input string s and keep track of the number of open and close parentheses.
  • We will remove the extra closing parentheses ) by comparing the number of open and close parentheses.
  • After that, we will remove the extra open parentheses ( by iterating through the string in reverse order.
Time Complexity O(n)

Same as the previous solution, the time complexity is O(n).

Space Complexity O(n)
  1. Creating the string ans
    • The space required for the ans string depends on the number of characters that need to be retained.
    • In the worst case, all characters in the input string are retained, so the space complexity is O(n), where n is the length of the input string s.
  2. Additional variables (close, n, curopen, curclose, i)
    • These variables are integers and do not depend on the size of the input string. They consume constant space.
    • It has nothing do with size of input string s as they have a fixed amount of memory.
    • Space complexity: O(1).

This approach involves iteratively scanning the input string from both ends and removing unmatched parentheses until all parentheses are balanced. Although both solutions have a space complexity of O(n), Solution 2 may perform better than Solution 1 due to its iterative removal of unmatched parentheses, potentially resulting in smaller intermediate input sizes.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function minRemoveToMakeValid(s: string): string {
    let close = s.split('').filter(char => char === ')').length;
    let ans = '';
    const n = s.length;
    let curopen = 0;
    let curclose = 0;

    for (let i = 0; i < n; i++) {
        if (s[i] === '(') {
            if (curopen < close) {
                ans += '(';
                curopen++;
            }
        } else if (s[i] === ')') {
            if (curopen === curclose) {
                close--;
            } else {
                curclose++;
                ans += ')';
            }
        } else {
            ans += s[i];
        }
    }

    return ans;
}
by yashnatani28

  1. Stack (abstract data type) ↩

  2. Approach 2 in C++ by @akash2099 ↩