LeetCode 301: Remove Invalid Parentheses Solution

Master LeetCode problem 301 (Remove Invalid Parentheses), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

301. Remove Invalid Parentheses

Hard

String Backtracking Breadth-First Search

Problem Explanation

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.

Solution Code

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;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 301 (Remove Invalid Parentheses)?

This page provides optimized solutions for LeetCode problem 301 (Remove Invalid Parentheses) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 301 (Remove Invalid Parentheses)?

The time complexity for LeetCode 301 (Remove Invalid Parentheses) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 301 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 301 in Java, C++, or Python.

Back to LeetCode Solutions