Remove Invalid Parentheses and Expression Parsing

from collections import deque

def removeInvalidParentheses(s):
    def is_valid(st):
        count = 0
        for c in st:
            if c == '(': count += 1
            elif c == ')':
                count -= 1
                if count < 0: return False
        return count == 0

    visited = {s}
    queue = deque([s])
    result = []
    found = False

    while queue:
        level_strings = []
        while queue:
            curr = queue.popleft()
            if is_valid(curr):
                result.append(curr)
                found = True
            if not found:
                for i in range(len(curr)):
                    if curr[i] in '()':
                        new_s = curr[:i] + curr[i+1:]
                        if new_s not in visited:
                            visited.add(new_s)
                            level_strings.append(new_s)
        if found: break
        queue.extend(level_strings)

    return result or ['']

# DFS approach: compute min removals first
def removeInvalidDFS(s):
    # Count minimum removals needed
    open_needed = close_needed = 0
    for c in s:
        if c == '(':
            open_needed += 1
        elif c == ')':
            if open_needed > 0: open_needed -= 1
            else: close_needed += 1

    result = set()
    def bt(idx, open_count, close_count, open_rem, close_rem, current):
        if idx == len(s):
            if open_rem == 0 and close_rem == 0:
                result.add(current)
            return
        ch = s[idx]
        # Option 1: remove this character
        if ch == '(' and open_rem > 0:
            bt(idx+1, open_count, close_count, open_rem-1, close_rem, current)
        if ch == ')' and close_rem > 0:
            bt(idx+1, open_count, close_count, open_rem, close_rem-1, current)
        # Option 2: keep this character
        bt(idx+1,
           open_count + (ch=='('),
           close_count + (ch==')'),
           open_rem, close_rem, current+ch) if (ch!=')'or open_count>close_count) or ch not in '()' else None

    bt(0, 0, 0, open_needed, close_needed, '')
    return list(result)

#include <bits/stdc++.h>
using namespace std;

vector<string> removeInvalidParentheses(string s) {
    // Count min removals
    int openRem = 0, closeRem = 0;
    for (char c : s) {
        if (c == '(') openRem++;
        else if (c == ')') {
            if (openRem > 0) openRem--;
            else closeRem++;
        }
    }

    set<string> result;
    function<void(int,int,int,int,int,string)> bt = [&](int i, int open, int close, int oRem, int cRem, string curr) {
        if (i == (int)s.size()) {
            if (oRem == 0 && cRem == 0) result.insert(curr);
            return;
        }
        char c = s[i];
        // Remove
        if (c == '(' && oRem > 0) bt(i+1, open, close, oRem-1, cRem, curr);
        if (c == ')' && cRem > 0) bt(i+1, open, close, oRem, cRem-1, curr);
        // Keep
        if (c != '(' && c != ')') bt(i+1, open, close, oRem, cRem, curr+c);
        else if (c == '(') bt(i+1, open+1, close, oRem, cRem, curr+c);
        else if (open > close) bt(i+1, open, close+1, oRem, cRem, curr+c);
    };
    bt(0, 0, 0, openRem, closeRem, "");
    return vector<string>(result.begin(), result.end());
}