Minimum Remove to Make Valid Parentheses
Given a string s with '(' , ')' and a-z.
try to remove the minimum number of parentheses '(' or ')' so that the resulting parentheses string is valid and return any valid string.
A valid String is:
- the empty string,
- string contains balanced ( and )
For Example:
Given String "ab(c(d)e)fg)"
Output: "ab(c(d)e)fg"
Explanation: "ab(c(de)fg)" , "ab(c(d)efg)" are all correct answers.
Input: "))(("
Output: ""
Solution
We can use a stack to push in all the '(', whenever we meet ')', we pop the '('. If the stack is empty and we meet a ')', this ')' should be removed from the original string.
Another approach is to have a two pass of string. During the first pass, we remove all the extra ')', during the second pass, we remove extra '('. The time complexity is O(N), the space complexity is O(N) since we need a StringBuilder to construct the string.
public class BalanceParentheses {
public static String balanced(String str) {
String firstPass = removeInvalid(str, '(', ')');
return removeInvalid(firstPass, ')', '(');
}
private static String removeInvalid(String str, char start, char end) {
//d)c(ba
StringBuilder sb = new StringBuilder();
int count = 0;
for(int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if(c == start) count++;
else if(c == end) {
if(count==0) continue;
count--;
}
sb.append(c);
}
return sb.reverse().toString(); //ab(c)d
}
public static void main(String...args) {
System.out.println(balanced("a)b(c)d"));
System.out.println(balanced("))(("));
System.out.println(balanced("lee(t(c)o)de)"));
}
}
public static String balanced(String str) {
String firstPass = removeInvalid(str, '(', ')');
return removeInvalid(firstPass, ')', '(');
}
private static String removeInvalid(String str, char start, char end) {
//d)c(ba
StringBuilder sb = new StringBuilder();
int count = 0;
for(int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if(c == start) count++;
else if(c == end) {
if(count==0) continue;
count--;
}
sb.append(c);
}
return sb.reverse().toString(); //ab(c)d
}
public static void main(String...args) {
System.out.println(balanced("a)b(c)d"));
System.out.println(balanced("))(("));
System.out.println(balanced("lee(t(c)o)de)"));
}
}
Time complexity O(N), space complexity O(N).
