301. Remove Invalid Parentheses

/**
 * Problem: LeetCode 301 - Remove Invalid Parentheses
 * Difficulty: Hard
 * Language: Java
 * Author: CodeByTushu
 */
import java.util.ArrayList;
import java.util.List;

/**
 * Problem: LeetCode 301 - Remove Invalid Parentheses
 * Difficulty: Hard
 * Language: Java
 * Author: CodeByTushu
 */
class Solution {
    public List<String> removeInvalidParentheses(String s) {
        int leftRem = 0, rightRem = 0;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                leftRem++;
            } else if (c == ')') {
                if (leftRem > 0) leftRem--;
                else rightRem++;
            }
        }

        List<String> result = new ArrayList<>();
        dfs(s, 0, leftRem, rightRem, result);
        return result;
    }

    private void dfs(String s, int start, int leftRem, int rightRem, List<String> result) {
        if (leftRem == 0 && rightRem == 0) {
            if (isValid(s)) result.add(s);
            return;
        }

        for (int i = start; i < s.length(); i++) {
            // Skip duplicates
            if (i > start && s.charAt(i) == s.charAt(i - 1)) continue;

            char c = s.charAt(i);
            if (c != '(' && c != ')') continue;

            String next = s.substring(0, i) + s.substring(i + 1);

            if (c == '(' && leftRem > 0) {
                dfs(next, i, leftRem - 1, rightRem, result);
            } else if (c == ')' && rightRem > 0) {
                dfs(next, i, leftRem, rightRem - 1, result);
            }
        }
    }

    private boolean isValid(String s) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') count++;
            else if (c == ')') {
                count--;
                if (count < 0) return false;
            }
        }
        return count == 0;
    }
}

"""
Problem: LeetCode 301 - Remove Invalid Parentheses
Difficulty: Hard
Language: Python
Author: CodeByTushu
"""
from typing import List

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        left_rem = 0
        right_rem = 0

        for c in s:
            if c == '(':
                left_rem += 1
            elif c == ')':
                if left_rem > 0:
                    left_rem -= 1
                else:
                    right_rem += 1

        result = []

        def is_valid(string: str) -> bool:
            count = 0
            for char in string:
                if char == '(':
                    count += 1
                elif char == ')':
                    count -= 1
                    if count < 0:
                        return False
            return count == 0

        def dfs(string: str, start: int, left: int, right: int):
            if left == 0 and right == 0:
                if is_valid(string):
                    result.append(string)
                return

            for i in range(start, len(string)):
                # Skip duplicate adjacent removals to prevent redundant branches
                if i > start and string[i] == string[i - 1]:
                    continue

                c = string[i]
                if c != '(' and c != ')':
                    continue

                next_str = string[:i] + string[i + 1:]

                if c == '(' and left > 0:
                    dfs(next_str, i, left - 1, right)
                elif c == ')' and right > 0:
                    dfs(next_str, i, left, right - 1)

        dfs(s, 0, left_rem, right_rem)
        return result

/**
 * Problem: LeetCode 301 - Remove Invalid Parentheses
 * Difficulty: Hard
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <string>

using namespace std;

/**
 * Problem: LeetCode 301 - Remove Invalid Parentheses
 * Difficulty: Hard
 * Language: C++
 * Author: CodeByTushu
 */
class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        int leftRem = 0, rightRem = 0;

        for (char c : s) {
            if (c == '(') {
                leftRem++;
            } else if (c == ')') {
                if (leftRem > 0) leftRem--;
                else rightRem++;
            }
        }

        vector<string> result;
        dfs(s, 0, leftRem, rightRem, result);
        return result;
    }

private:
    void dfs(const string& s, int start, int leftRem, int rightRem, vector<string>& result) {
        if (leftRem == 0 && rightRem == 0) {
            if (isValid(s)) result.push_back(s);
            return;
        }

        for (int i = start; i < s.length(); i++) {
            // Skip duplicates
            if (i > start && s[i] == s[i - 1]) continue;

            char c = s[i];
            if (c != '(' && c != ')') continue;

            string next = s.substr(0, i) + s.substr(i + 1);

            if (c == '(' && leftRem > 0) {
                dfs(next, i, leftRem - 1, rightRem, result);
            } else if (c == ')' && rightRem > 0) {
                dfs(next, i, leftRem, rightRem - 1, result);
            }
        }
    }

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

/**
 * Problem: LeetCode 301 - Remove Invalid Parentheses
 * Difficulty: Hard
 * Language: JavaScript
 * Author: CodeByTushu
 */
var removeInvalidParentheses = function(s) {
    let leftRem = 0;
    let rightRem = 0;

    for (let i = 0; i < s.length; i++) {
        const c = s[i];
        if (c === '(') {
            leftRem++;
        } else if (c === ')') {
            if (leftRem > 0) leftRem--;
            else rightRem++;
        }
    }

    const result = [];

    const isValid = (str) => {
        let count = 0;
        for (let i = 0; i < str.length; i++) {
            const c = str[i];
            if (c === '(') count++;
            else if (c === ')') {
                count--;
                if (count < 0) return false;
            }
        }
        return count === 0;
    };

    const dfs = (str, start, left, right) => {
        if (left === 0 && right === 0) {
            if (isValid(str)) result.push(str);
            return;
        }

        for (let i = start; i < str.length; i++) {
            // Skip duplicates
            if (i > start && str[i] === str[i - 1]) continue;

            const c = str[i];
            if (c !== '(' && c !== ')') continue;

            const next = str.slice(0, i) + str.slice(i + 1);

            if (c === '(' && left > 0) {
                dfs(next, i, left - 1, right);
            } else if (c === ')' && right > 0) {
                dfs(next, i, left, right - 1);
            }
        }
    };

    dfs(s, 0, leftRem, rightRem);
    return result;
};