301. Remove Invalid Parentheses

Explanation

To solve this problem, we can use a breadth-first search (BFS) approach. We start by adding the input string into a queue. Then, we iterate over the queue, removing one character at a time, and check if the resulting string is valid. If it is valid, we add it to the result list. If not, we add the modified string back to the queue for further processing. We continue this process until we find all valid strings with the minimum number of removals.

Algorithm:

Initialize a queue and a visited set.
Add the input string to the queue and mark it as visited.
While the queue is not empty:
- Remove the first element from the queue.
- Check if the removed string is valid:
  - If valid, add it to the result list.
  - If not valid, generate all possible strings by removing one character at a time and add them to the queue if not visited.
Return the result list.

Time Complexity:

The time complexity of this algorithm is O(2^N), where N is the length of the input string. This is because for each character in the string, we have two choices - either remove it or keep it.

Space Complexity:

The space complexity of this algorithm is O(N), where N is the length of the input string. This is because we are using a queue and a visited set to store intermediate results.

View Leetcode Problem

import java.util.*;

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> result = new ArrayList<>();
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        
        queue.offer(s);
        visited.add(s);
        
        while (!queue.isEmpty()) {
            String current = queue.poll();
            if (isValid(current)) {
                result.add(current);
            } else {
                for (int i = 0; i < current.length(); i++) {
                    if (current.charAt(i) == '(' || current.charAt(i) == ')') {
                        String next = current.substring(0, i) + current.substring(i + 1);
                        if (!visited.contains(next)) {
                            queue.offer(next);
                            visited.add(next);
                        }
                    }
                }
            }
        }
        
        return result;
    }
    
    private boolean isValid(String s) {
        int count = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                count++;
            } else if (c == ')') {
                count--;
                if (count < 0) return false;
            }
        }
        return count == 0;
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

Add import statement if required.
Optimize the code for better time or space complexity.
Add test cases to validate edge cases and common scenarios.
Handle error conditions or invalid inputs gracefully.
Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.