Facebook
Google
Leetcode
GeeksForGeeks
Youtube
Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.
Return a list of unique strings that are valid with the minimum number of removals. You may return the answer in any order.
Test Cases
Example 1:
Input: s = "()())()"
Output: ["(())()","()()()"]
Example 2:
Input: s = "(a)())()"
Output: ["(a())()","(a)()()"]
Example 3:
Input: s = ")("
Output: [""]
Constraints:
1 <= s.length <= 25sconsists of lowercase English letters and parentheses'('and')'.- There will be at most
20parentheses ins.
Solution
class Solution {
public List<String> removeInvalidParentheses(String s) {
Queue<String> queue = new LinkedList<>();
Set<String> visited = new HashSet<>();
List<String> result = new ArrayList<>();
boolean found = false;
queue.offer(s);
visited.add(s);
while(!queue.isEmpty()) {
String current = queue.poll();
if (isValid(current)) {
result.add(current);
found = true;
}
if (found) {
continue;
}
for(int i=0; i<current.length(); i++) {
char c = current.charAt(i);
if (c != '(' && c != ')') {
continue;
}
String next = current.substring(0, i) + current.substring(i+1);
if (!visited.contains(next)) {
visited.add(next);
queue.offer(next);
}
}
}
return result;
}
private boolean isValid(String s) {
int count = 0;
for(char c: s.toCharArray()) {
if (c == '(') {
count++;
}
else if (c == ')'){
if (count == 0) {
return false;
}
count--;
}
}
return count == 0;
}
}