|
| 1 | +/* |
| 2 | +* [1249] Minimum Remove to Make Valid Parentheses * |
| 3 | +
|
| 4 | +Given a string s of '(' , ')' and lowercase English characters. |
| 5 | +
|
| 6 | +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. |
| 7 | +
|
| 8 | +Formally, a parentheses string is valid if and only if: |
| 9 | +
|
| 10 | + It is the empty string, contains only lowercase characters, or |
| 11 | + It can be written as AB (A concatenated with B), where A and B are valid strings, or |
| 12 | + It can be written as (A), where A is a valid string. |
| 13 | +
|
| 14 | +Example 1: |
| 15 | +
|
| 16 | +Input: s = "lee(t(c)o)de)" |
| 17 | +Output: "lee(t(c)o)de" |
| 18 | +Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted. |
| 19 | +
|
| 20 | +Time: O(n) |
| 21 | +Space: O(n) |
| 22 | +
|
| 23 | +Runtime: 14 ms, faster than 98.14% of C++ online submissions for Minimum Remove to Make Valid Parentheses. |
| 24 | +Memory Usage: 14.2 MB, less than 10.57% of C++ online submissions for Minimum Remove to Make Valid Parentheses. |
| 25 | +*/ |
| 26 | + |
| 27 | + |
| 28 | + |
| 29 | +classSolution { |
| 30 | +public: |
| 31 | + stringminRemoveToMakeValid(string s) { |
| 32 | + stack<pair<char,int>> st; |
| 33 | + |
| 34 | +for (int i =0; i < s.size(); i++) { |
| 35 | +if (s[i] =='(') { |
| 36 | + st.push(make_pair(s[i], i)); |
| 37 | + }elseif (s[i] ==')') { |
| 38 | +if (!st.empty()and st.top().first =='(') { |
| 39 | + st.pop(); |
| 40 | + }else { |
| 41 | + st.push(make_pair(')', i)); |
| 42 | + } |
| 43 | + } |
| 44 | + } |
| 45 | + |
| 46 | +while (!st.empty()) { |
| 47 | + s.erase(s.begin() + st.top().second); |
| 48 | + st.pop(); |
| 49 | + } |
| 50 | + |
| 51 | +return s; |
| 52 | + } |
| 53 | +}; |