Algorithm to Find Minimum Removals to Make Valid Parentheses

  • Time:2020-09-10 13:03:17
  • Class:Weblog
  • Read:24

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) —

Recommend:
How to Avoid Paying Too Much Fee when Cashing out Bitcoin via Wi
The Common Kodi Errors and Use of Free VPN for Linux
Java Pattern: Use Atomic Boolean to Return Single Usage Object
Significance of HTML and CSS in Mobile App Development
How to Reverse Words in a String using Modern Programming Langua
The Python Function to Retrieve the Producer Reward for Witness
Function to Compute the Average Salary Excluding the Minimum and
Efficient Algorithms to Compute The kth Factor of a Natural Numb
Can We Make Arithmetic Progression From Sequence of Numbers?
How to SSH to Remote Host using the Priviate/Public Keys Authent
Share:Facebook Twitter
Comment list
Comment add