LeetCode [1249] Minimum Remove to Make Valid Parentheses

 1249. Minimum Remove to Make Valid Parentheses

Medium

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.

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 41 42 43

class Solution { public String minRemoveToMakeValid(String s) { String s1 = trim1(s); String s2 = trim2(new StringBuilder(s1).reverse().toString()); return new StringBuilder(s2).reverse().toString(); } String trim1(String s){ int l = 0, r = 0; StringBuilder sb = new StringBuilder(); for(char ch : s.toCharArray()){ boolean skip = false; if(ch=='(') l++; if(ch==')'){ r++; if(r>l){ skip = true; r--; } } if(!skip) sb.append(ch); } return sb.toString(); } String trim2(String s){ int l = 0, r = 0; StringBuilder sb = new StringBuilder(); for(char ch : s.toCharArray()){ boolean skip = false; if(ch==')') r++; if(ch=='('){ l++; if(l>r){ skip = true; l--; } } if(!skip) sb.append(ch); } return sb.toString(); } }

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

class Solution { public String minRemoveToMakeValid(String s) { Stack<Integer> stk = new Stack<>(); StringBuilder sb = new StringBuilder(s); int n = sb.length(); for(int i=0; i<n; ++i){ if(s.charAt(i)=='('){ stk.add(i); }else if(s.charAt(i)==')'){ if(!stk.isEmpty()){ stk.pop(); }else{//extra ')', remove sb.setCharAt(i, '*'); } } } while(!stk.isEmpty()){ int i = stk.pop(); sb.setCharAt(i, '*'); } return sb.toString().replaceAll("\\*", ""); } }