This is a Leetcode problem –

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note –

The input string may contain letters other than the parentheses`(`

and`)`

.

`def remove_invalid_parentheses(s): removed = 0 results = {s} count = {"(": 0, ")": 0} for i, c in enumerate(s): if c == ")" and count["("] == count[")"]: new_results = set() while results: result = results.pop() for j in range(i - removed + 1): if result[j] == ")": new_results.add(result[:j] + result[j + 1:]) results = new_results removed += 1 else: if c in count: count[c] += 1 count = {"(": 0, ")": 0} i = len(s) ll = len(s) - removed for ii in range(ll - 1, -1, -1): i-=1 c = s[i] if c == "(" and count["("] == count[")"]: new_results = set() while results: result = results.pop() for j in range(ii, ll): if result[j] == "(": new_results.add(result[:j] + result[j + 1:]) results = new_results ll -= 1 else: if c in count: count[c] += 1 return list(results) `

Explanation –

- Scan from left to right, make sure
`count["("] >= count[")"]`

. - Then scan from right to left, make sure
`count["("] <= count[")"]`

.

Here are some inputs/outputs –

`print(remove_invalid_parentheses("()())()")) >>> ["()()()", "(())()"] print(remove_invalid_parentheses("(a)())()")) >>> ["(a)()()", "(a())()"] print(remove_invalid_parentheses(")(")) >>> [""] `

Here are the times taken for each output –

`%timeit remove_invalid_parentheses("()())()") 6.54 µs ± 176 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) %timeit remove_invalid_parentheses("(a)())()") 8.43 µs ± 1.29 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each) %timeit remove_invalid_parentheses(")(") 3.69 µs ± 67.3 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) `

So, I would like to know whether I could make this program shorter and more efficient.

Any help would be highly appreciated.