Remove Invalid Parentheses solution and explanation

from collections import deque

def removeInvalidParentheses(s):
    def isValid(string):
        balance = 0
        for char in string:
            if char == '(': balance += 1
            if char == ')': balance -= 1
            if balance < 0: return False
        return balance == 0
    
    queue = deque([s])
    visited = set([s])
    found = False
    valid_expressions = []

    while queue:
        expression = queue.popleft()
        
        if isValid(expression):
            found = True
            valid_expressions.append(expression)
        
        if found:
            continue
        
        for i in range(len(expression)):
            if expression[i] not in ('(', ')'):
                continue
            next_expression = expression[:i] + expression[i+1:]
            if next_expression not in visited:
                visited.add(next_expression)
                queue.append(next_expression)

    return valid_expressions

#include <iostream>
#include <queue>
#include <unordered_set>
#include <vector>
using namespace std;

bool isValid(const string &s) {
    int balance = 0;
    for (char c : s) {
        if (c == '(') balance++;
        if (c == ')') balance--;
        if (balance < 0) return false;
    }
    return balance == 0;
}

vector<string> removeInvalidParentheses(string s) {
    unordered_set<string> visited;
    queue<string> q;
    vector<string> result;
    q.push(s);
    visited.insert(s);
    bool found = false;
    
    while (!q.empty()) {
        string str = q.front(); q.pop();
        
        if (isValid(str)) {
            found = true;
            result.push_back(str);
        }

        if (found) continue;

        for (size_t i = 0; i < str.length(); ++i) {
            if (str[i] != '(' && str[i] != ')') continue;
            string next = str.substr(0, i) + str.substr(i + 1);
            if (!visited.count(next)) {
                visited.insert(next);
                q.push(next);
            }
        }
    }
    return result;
}

import java.util.HashSet;
import java.util.Set;

public class RemoveInvalidParentheses {

    public List<String> removeInvalidParentheses(String s) {
        Set<String> results = new HashSet<>();
        int[] minRemoved = {Integer.MAX_VALUE};
        
        int balance = 0, leftRem = 0, rightRem = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                leftRem++;
            } else if (c == ')') {
                if (leftRem == 0) rightRem++;
                else leftRem--;
            }
        }

        dfs(s, 0, 0, 0, leftRem, rightRem, new StringBuilder(), results, 0, minRemoved);

        return new ArrayList<>(results);
    }

    private void dfs(String s, int index, int leftCount, int rightCount, int leftRem, int rightRem, StringBuilder expression, Set<String> results, int removed, int[] minRemoved) {
        if (index == s.length()) {
            if (leftRem == 0 && rightRem == 0) {
                if (removed <= minRemoved[0]) {
                    if (removed < minRemoved[0]) {
                        results.clear();
                        minRemoved[0] = removed;
                    }
                    results.add(expression.toString());
                }
            }
            return;
        }

        char currentChar = s.charAt(index);
        int length = expression.length();

        if ((currentChar == '(' && leftRem > 0) || (currentChar == ')' && rightRem > 0)) {
            dfs(s, index + 1, leftCount, rightCount, leftRem - (currentChar == '(' ? 1 : 0), rightRem - (currentChar == ')' ? 1 : 0), expression, results, removed + 1, minRemoved);
        }

        expression.append(currentChar);

        if (currentChar != '(' && currentChar != ')') {
            dfs(s, index + 1, leftCount, rightCount, leftRem, rightRem, expression, results, removed, minRemoved);
        } else if (currentChar == '(') {
            dfs(s, index + 1, leftCount + 1, rightCount, leftRem, rightRem, expression, results, removed, minRemoved);
        } else if (rightCount < leftCount) {
            dfs(s, index + 1, leftCount, rightCount + 1, leftRem, rightRem, expression, results, removed, minRemoved);
        }

        expression.deleteCharAt(length);
    }
}

function removeInvalidParentheses(s) {
    const isValid = (str) => {
        let count = 0;
        for (let char of str) {
            if (char === '(') count++;
            if (char === ')') count--;
            if (count < 0) return false;
        }
        return count === 0;
    };

    let results = new Set();
    let minRemoved = Infinity;

    const dfs = (str, start, l, r, removed) => {
        if (removed > minRemoved) return;
        if (l === 0 && r === 0) {
            if (isValid(str)) {
                if (removed < minRemoved) {
                    results.clear();
                    minRemoved = removed;
                }
                results.add(str);
            }
            return;
        }

        for (let i = start; i < str.length; i++) {
            if (i > start && str[i] === str[i - 1]) continue; // Skip duplicate
            if (str[i] === '(' && l > 0) {
                dfs(str.slice(0, i) + str.slice(i + 1), i, l - 1, r, removed + 1);
            }
            if (str[i] === ')' && r > 0) {
                dfs(str.slice(0, i) + str.slice(i + 1), i, l, r - 1, removed + 1);
            }
        }
    };

    let leftRem = 0, rightRem = 0;
    for (let char of s) {
        if (char === '(') leftRem++;
        if (char === ')') {
            if (leftRem === 0) rightRem++;
            else leftRem--;
        }
    }

    dfs(s, 0, leftRem, rightRem, 0);
    return Array.from(results);
}

func removeInvalidParentheses(s string) []string {
	vis := map[string]bool{}
	l, r, n := 0, 0, len(s)
	for _, c := range s {
		if c == '(' {
			l++
		} else if c == ')' {
			if l > 0 {
				l--
			} else {
				r++
			}
		}
	}
	var dfs func(i, l, r, lcnt, rcnt int, t string)
	dfs = func(i, l, r, lcnt, rcnt int, t string) {
		if i == n {
			if l == 0 && r == 0 {
				vis[t] = true
			}
			return
		}
		if n-i < l+r || lcnt < rcnt {
			return
		}
		if s[i] == '(' && l > 0 {
			dfs(i+1, l-1, r, lcnt, rcnt, t)
		}
		if s[i] == ')' && r > 0 {
			dfs(i+1, l, r-1, lcnt, rcnt, t)
		}
		x, y := 0, 0
		if s[i] == '(' {
			x = 1
		} else if s[i] == ')' {
			y = 1
		}
		dfs(i+1, l, r, lcnt+x, rcnt+y, t+string(s[i]))
	}
	dfs(0, l, r, 0, 0, "")
	ans := make([]string, 0, len(vis))
	for v := range vis {
		ans = append(ans, v)
	}
	return ans
}