Algorithm to Find Minimum Removals to Make Valid Parentheses
- Time:2020-09-10 13:03:17
- Class:Weblog
- Read:27
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:DFS and BFS Algorithms to Find All the Lonely Nodes of a Binary
Three ways of Running a continuous NodeJS Application on Your Se
K Closest Points to Origin using Custom Sorting Algorithm in C++
Using Hash Set to Determine if a String is the Permutation of An
Recursive Algorithm to Get Proxy Votes on Steem Blockchain
Ways to spot SEO scam – Signs that tell you about scam SEO compa
5 Evergreen Content Marketing Ideas for Virtually Any Business
3 Ways to Brainstorm New Blog Content
7 Good Blogger Tools For Working From Home
Can You Earn Bitcoin With Blogging?
- Comment list
-
- Comment add