HomeLeetcode301. Remove Invalid Parentheses - Leetcode Solutions
Leetcode

301. Remove Invalid Parentheses – Leetcode Solutions

Declan Clarke

Description

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.

Examples:

Example 1:

Input: s = "()())()"
Output: ["(())()","()()()"]

Example 2:

Input: s = "(a)())()"
Output: ["(a())()","(a)()()"]

Example 3:

Input: s = ")("
Output: [""]

Solution in Python

Key Concepts:

  1. Parentheses Validity:
    • A string of parentheses is valid if, at any point, the number of closing parentheses ) does not exceed the number of opening parentheses (, and at the end of the string, both counts are equal.
  2. BFS for Minimizing Removals:
    • We can use BFS to explore all possible strings formed by removing parentheses. The first time we find valid strings, they are the ones with the minimum number of removals since BFS explores solutions level by level (i.e., removing 1, 2, 3, etc. parentheses).
  3. Avoiding Duplicates:
    • Since multiple paths can lead to the same string, we store seen strings in a set to avoid processing the same string multiple times.
  4. Stopping Early:
    • As soon as we find valid strings, we stop further exploration at that level (i.e., the shortest solution).
Python
from collections import deque

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        # Helper function to check if a string is valid (well-formed parentheses)
        def is_valid(string):
            balance = 0
            for char in string:
                if char == '(':
                    balance += 1
                elif char == ')':
                    balance -= 1
                # If balance goes negative, we have more ')' than '(' at some point
                if balance < 0:
                    return False
            # Valid if balance is zero at the end
            return balance == 0

        # BFS setup
        # Queue for BFS (starting with the original string)
        queue = deque([s])
        # Set to avoid reprocessing the same string
        visited = set([s])
        # To store the valid results
        result = []
        # Flag to indicate when we've found the first valid string
        found = False

        while queue:
            current = queue.popleft()
            
            # If the current string is valid, we add it to the results
            if is_valid(current):
                result.append(current)
                found = True
            
            # If we found a valid string, no need to generate further strings at this level
            if found:
                continue
            
            # Generate all possible states by removing one parenthesis at a time
            for i in range(len(current)):
                if current[i] not in ('(', ')'):
                    continue  # Skip non-parenthesis characters
                
                # Create a new string by removing the current character
                new_string = current[:i] + current[i+1:]
                
                # If this new string hasn't been processed yet, add it to the queue
                if new_string not in visited:
                    visited.add(new_string)
                    queue.append(new_string)

        return result

Explanation:

  1. Helper Function (is_valid):
    • This function checks if a given string is a valid parentheses string. It iterates over the string, maintaining a balance of open and close parentheses. If the balance becomes negative at any point (i.e., more ) than (), the string is invalid. The string is valid if the balance is 0 at the end.
  2. BFS Setup:
    • We initialize a queue for the BFS process and a set to keep track of visited strings (to avoid redundant checks). The queue initially contains the input string s.
  3. Main BFS Loop:
    • For each string current in the queue, we first check if it’s valid using the is_valid function.
    • If it’s valid, we add it to the result list and set the found flag to True. Once we’ve found valid strings, we continue the loop but do not generate new strings for further exploration from that level.
    • If the string is not valid and we haven’t yet found a valid one, we generate all possible strings by removing one parenthesis at a time and enqueue them for further exploration if they haven’t been visited.
  4. Early Stopping:
    • As soon as we find valid strings at any level of BFS, we stop generating new strings at deeper levels, as they would have more removals and are unnecessary for the solution.
  5. Return:
    • After the BFS completes, we return the result list containing all the valid strings with the minimum number of parentheses removals.

Time Complexity:

  • The worst-case time complexity is O(2n), where n is the length of the string. This is because each character can either be included or excluded, leading to up to 2n possible strings. However, we optimize by stopping as soon as we find valid strings and avoiding duplicates.

Space Complexity:

  • The space complexity is O(2n) for the queue and the visited set, as we may store up to 2n unique strings.

Example Walkthrough:

For the input string s = "()())()", the BFS process would explore:

  1. Level 0 (Initial string): ()())()
  2. Level 1 (One removal): )())(), (())(), ()()(), ()())), ()())(, etc.
  3. At level 1, valid strings are found: "(())()" and "()()()". The process stops, and these are returned.

Solution in C++

C++
#include <vector>
#include <string>
#include <queue>
#include <unordered_set>

using namespace std;

class Solution {
public:
    // Helper function to check if a string has valid parentheses
    bool isValid(const string& str) {
        int balance = 0;
        for (char c : str) {
            if (c == '(') {
                balance++;
            } else if (c == ')') {
                balance--;
            }
            // If at any point balance goes negative, there are too many closing parentheses
            if (balance < 0) {
                return false;
            }
        }
        // A valid string must have balance 0 at the end
        return balance == 0;
    }
    
    // Function to remove invalid parentheses
    vector<string> removeInvalidParentheses(string s) {
        vector<string> result;
        unordered_set<string> visited;  // To keep track of already visited strings
        queue<string> q;  // Queue for BFS
        
        // Start BFS with the original string
        q.push(s);
        visited.insert(s);
        
        bool found = false;  // Flag to indicate when we've found a valid string
        
        while (!q.empty()) {
            string current = q.front();
            q.pop();
            
            // If the current string is valid, add it to the result
            if (isValid(current)) {
                result.push_back(current);
                found = true;
            }
            
            // If a valid string has been found, we don't generate further strings
            if (found) continue;
            
            // Generate all possible strings by removing one parenthesis at a time
            for (int i = 0; i < current.length(); i++) {
                // Skip non-parenthesis characters
                if (current[i] != '(' && current[i] != ')') continue;
                
                // Create a new string by removing the current character
                string next = current.substr(0, i) + current.substr(i + 1);
                
                // If the new string hasn't been visited yet, add it to the queue
                if (visited.find(next) == visited.end()) {
                    q.push(next);
                    visited.insert(next);
                }
            }
        }
        
        return result;
    }
};

Solution in Javascript

JavaScript
var removeInvalidParentheses = function(s) {
    // Helper function to check if a string has valid parentheses
    const isValid = (str) => {
        let balance = 0;  // Counter for the balance of parentheses
        for (const char of str) {
            if (char === '(') {
                balance++;  // Increment for opening parenthesis
            } else if (char === ')') {
                balance--;  // Decrement for closing parenthesis
            }
            // If balance goes negative, there are too many closing parentheses
            if (balance < 0) {
                return false;  // Invalid string
            }
        }
        return balance === 0;  // Valid string must have balance 0
    };

    const result = [];  // Array to store the valid strings
    const visited = new Set();  // Set to track visited strings
    const queue = [];  // Queue for BFS
    
    // Start BFS with the original string
    queue.push(s);
    visited.add(s);
    
    let found = false;  // Flag to indicate when we find a valid string
    
    while (queue.length > 0) {
        const current = queue.shift();  // Get the front string from the queue
        
        // If the current string is valid, add it to the result
        if (isValid(current)) {
            result.push(current);
            found = true;  // We found at least one valid string
        }
        
        // If we found a valid string, do not generate further strings
        if (found) continue;
        
        // Generate all possible strings by removing one parenthesis at a time
        for (let i = 0; i < current.length; i++) {
            // Skip non-parenthesis characters
            if (current[i] !== '(' && current[i] !== ')') continue;
            
            // Create a new string by removing the current character
            const next = current.slice(0, i) + current.slice(i + 1);
            
            // If the new string hasn't been visited yet, add it to the queue
            if (!visited.has(next)) {
                queue.push(next);
                visited.add(next);
            }
        }
    }
    
    return result;  // Return the list of valid strings
};

Solution in Java

Java
import java.util.*;

class Solution {
    // Main function to remove invalid parentheses
    public List<String> removeInvalidParentheses(String s) {
        List<String> result = new ArrayList<>(); // List to store valid strings
        Set<String> visited = new HashSet<>(); // Set to track visited strings
        Queue<String> queue = new LinkedList<>(); // Queue for BFS

        // Start BFS with the original string
        queue.add(s);
        visited.add(s);

        boolean found = false; // Flag to indicate when we find a valid string

        while (!queue.isEmpty()) {
            String current = queue.poll(); // Get the front string from the queue

            // If the current string is valid, add it to the result
            if (isValid(current)) {
                result.add(current);
                found = true; // We found at least one valid string
            }

            // If we found a valid string, do not generate further strings
            if (found) continue;

            // Generate all possible strings by removing one parenthesis at a time
            for (int i = 0; i < current.length(); i++) {
                // Skip non-parenthesis characters
                if (current.charAt(i) != '(' && current.charAt(i) != ')') continue;

                // Create a new string by removing the current character
                String next = current.substring(0, i) + current.substring(i + 1);

                // If the new string hasn't been visited yet, add it to the queue
                if (!visited.contains(next)) {
                    queue.add(next);
                    visited.add(next);
                }
            }
        }

        return result; // Return the list of valid strings
    }

    // Helper function to check if a string has valid parentheses
    private boolean isValid(String str) {
        int balance = 0; // Counter for the balance of parentheses
        for (char ch : str.toCharArray()) {
            if (ch == '(') {
                balance++; // Increment for an opening parenthesis
            } else if (ch == ')') {
                balance--; // Decrement for a closing parenthesis
            }
            // If balance goes negative, there are too many closing parentheses
            if (balance < 0) {
                return false; // Invalid string
            }
        }
        return balance == 0; // Valid string must have balance 0
    }
}

Related Post

Subscribe
Notify of

0 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments

Popular

© 2024 Devexplain.com