Problem Statement
Given a string str consisting only of lowercase letters and the characters ( and ), your task is to delete the minimum number of parentheses so that the resulting string is balanced. A balanced string is defined as one where every opening parenthesis has a matching closing parenthesis in the correct order, and no extra closing parentheses appear. You need to print all distinct strings obtained by performing the minimum number of removals.
Example Inputs and Outputs
Example 1
Input: str = "()())()"
Output: ["()()()", "(())()"]
Explanation:
We can remove the closing bracket at index 3 to obtain the balanced string “()()()”. Similarly, we can remove the closing bracket at index 1 to obtain the balanced string “(())()”.
Example 2
Input: str = "(v)())()"
Output: ["(v)()()", "(v())()"]
Explanation:
In this case, letters do not affect the balance of parentheses. Removing the closing parenthesis at index 5 gives us “(v)()()”, and removing the closing parenthesis at index 2 gives us “(v())()”.
Example 3
Input: str = ")("
Output: [""]
Explanation:
The string is unbalanced, and removing both parentheses gives us an empty string.
Algorithm
To solve this problem effectively, we can use a Breadth-First Search (BFS) approach. The main steps are as follows:
- Define a Helper Function: Create a function
isValid(s)that checks if a stringsis balanced. - Use BFS to Explore All Possibilities:
- Initialize a queue to keep track of strings and the number of removals made.
- Use a set to keep track of visited strings to prevent processing the same string multiple times.
- Continue exploring strings until a valid balanced string is found or all possibilities are exhausted.
- Pruning: If the removal count exceeds the minimum found so far, stop exploring that path.
- Collect All Distinct Balanced Strings: When a valid string is found, compare its removal count with the minimum found so far and store it accordingly.
Python Solution
import collections
class Solution:
def isValid(self, s: str) -> bool:
balance = 0
for char in s:
if char == '(':
balance += 1
elif char == ')':
balance -= 1
if balance list[str]:
if not s:
return [""]
queue = collections.deque([(s, 0)]) # (string, removals_count)
visited = {s}
result = []
min_removals_found = float('inf')
while queue:
current_s, removals = queue.popleft()
# Stop exploring if we exceed the minimum removals found
if removals > min_removals_found:
continue
# If valid, check and store string
if self.isValid(current_s):
if removals < min_removals_found:
result = [current_s]
min_removals_found = removals
elif removals == min_removals_found:
result.append(current_s)
continue
# Generate children by removing parentheses
for i in range(len(current_s)):
if current_s[i] in ('(', ')'):
next_s = current_s[:i] + current_s[i+1:]
if next_s not in visited:
visited.add(next_s)
queue.append((next_s, removals + 1))
return sorted(list(set(result))) if result else [""]
# Testing the Python Solution
solver = Solution()
print(solver.removeInvalidParentheses("()())()")) # Output: ["()()()", "(())()"]
print(solver.removeInvalidParentheses("(v)())()")) # Output: ["(v)()()", "(v())()"]
print(solver.removeInvalidParentheses(")(")) # Output: [""]
Java Solution
import java.util.*;
class SolutionJava {
private boolean isValid(String s) {
int balance = 0;
for (char c : s.toCharArray()) {
if (c == '(') {
balance++;
} else if (c == ')') {
balance--;
}
if (balance < 0) {
return false;
}
}
return balance == 0;
}
public List removeInvalidParentheses(String s) {
if (s == null) {
return Collections.singletonList("");
}
Queue<Pair> queue = new LinkedList();
Set visited = new HashSet();
List result = new ArrayList();
int minRemovalsFound = Integer.MAX_VALUE;
queue.offer(new Pair(s, 0));
visited.add(s);
while (!queue.isEmpty()) {
Pair currentPair = queue.poll();
String currentS = currentPair.getKey();
int removals = currentPair.getValue();
// Check if we have already exceeded the minimum removals found
if (removals > minRemovalsFound) {
continue;
}
// Check for valid strings
if (isValid(currentS)) {
if (removals < minRemovalsFound) {
result.clear(); // Found a new minimum
result.add(currentS);
minRemovalsFound = removals;
} else if (removals == minRemovalsFound) {
result.add(currentS);
}
continue;
}
// Generate possible next states by removing one parenthesis
for (int i = 0; i < currentS.length(); i++) {
char charToRemove = currentS.charAt(i);
if (charToRemove == '(' || charToRemove == ')') {
String nextS = currentS.substring(0, i) + currentS.substring(i + 1);
if (!visited.contains(nextS)) {
visited.add(nextS);
queue.offer(new Pair(nextS, removals + 1));
}
}
}
}
// Ensure uniqueness and sort for consistent output
if (result.isEmpty()) {
return Collections.singletonList("");
}
Set distinctResults = new HashSet(result);
List sortedResults = new ArrayList(distinctResults);
Collections.sort(sortedResults);
return sortedResults;
}
// Helper Pair class
static class Pair {
private K key;
private V value;
public Pair(K key, V value) {
this.key = key;
this.value = value;
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
}
public static void main(String[] args) {
SolutionJava solver = new SolutionJava();
System.out.println(solver.removeInvalidParentheses("()())()")); // Output: ["()()()", "(())()"]
System.out.println(solver.removeInvalidParentheses("(v)())()")); // Output: ["(v)()()", "(v())()"]
System.out.println(solver.removeInvalidParentheses(")(")); // Output: [""]
}
}
Conclusion
This problem efficiently demonstrates how to utilize BFS for generating all correct and unique outcomes while manipulating strings. Both provided solutions in Python and Java follow the same logic and present clear implementations to achieve the desired results.
With Chinmay Murugkar 