Algorithm to Find Minimum Removals to Make Valid Parentheses

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.

Example 4:
Input: s = “(a(b(c)d)”
Output: “a(b(c)d)”

Constraints:
1 <= s.length <= 10^5
s[i] is one of ‘(‘ , ‘)’ and lowercase English letters.

Hints:
Each prefix of a balanced parentheses has a number of open parentheses greater or equal than closed parentheses, similar idea with each suffix.
Check the array from left to right, remove characters that do not meet the property mentioned above, same idea in backward way.

Two Passes Greedy

Recall that we use a variable balance to determine if a string contains pairs of parentheses i.e. increment the balance when we meet open parentheses and decrement the balance when we have closed parentheses. At any time when the balance falls negative, it is not a valid pair of parentheses string.

Thus, using greedy approach, we first scan from left to right, keep tracking of the balance variable, if it is a closed parentheses that makes the balance negative, we must remove it.

Similarly, the second pass is done from right to the left, removing the extra open parentheses (reversed pair).

Finally, we reverse the string. The complexity is O(N) time and O(1) constant space.

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
28
29
30
31
32
33
34
35
36
37
38
39
40

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        string a = "";
        int balance = 0;
        // from left to right
        for (const auto &n: s) {
            if (n == '(') {
                balance ++;
                a += n;
            } else if (n == ')') {
                if (balance > 0) {
                    a += n;
                    balance --;
                }
            } else {
                a += n;
            }
        }
        string b = "";
        balance = 0;
        // from right to left
        for (int i = a.size() - 1; i >= 0; -- i) {
            char n = a[i];
            if (n == ')') {
                balance ++;
                b += n;
            } else if (n == '(') {
                if (balance > 0) {
                    b += n;
                    balance --;
                }
            } else {
                b += n;
            }
        }      
        std::reverse(begin(b), end(b));
        return b;
    }
};

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        string a = "";
        int balance = 0;
        // from left to right
        for (const auto &n: s) {
            if (n == '(') {
                balance ++;
                a += n;
            } else if (n == ')') {
                if (balance > 0) {
                    a += n;
                    balance --;
                }
            } else {
                a += n;
            }
        }
        string b = "";
        balance = 0;
        // from right to left
        for (int i = a.size() - 1; i >= 0; -- i) {
            char n = a[i];
            if (n == ')') {
                balance ++;
                b += n;
            } else if (n == '(') {
                if (balance > 0) {
                    b += n;
                    balance --;
                }
            } else {
                b += n;
            }
        }      
        std::reverse(begin(b), end(b));
        return b;
    }
};

–EOF (The Ultimate Computing & Technology Blog) —