Loading problem…
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. A string is valid when every ')' has a matching '(' before it and every '(' is eventually closed — scanning left to right, the running balance of '(' minus ')' never drops below zero and ends at exactly zero. Letters are ignored for validity.
Example 1
Input: s = ()())()
Output: ["(())()","()()()"]
Explanation: There is one extra ')'. Removing it one way gives "(())()" and another way gives "()()()"; both are valid and each deletes just a single character.
Example 2
Input: s = (a)())()
Output: ["(a())()","(a)()()"]
Explanation: The letter 'a' is ignored for balancing. One stray ')' must go, and the two ways to drop it leave "(a())()" and "(a)()()".
Example 3
Input: s = )(
Output: [""]
Explanation: Neither parenthesis can be matched, so both are removed and the only valid result is the empty string.
Removing the fewest characters means exploring strings level by level — all 1-removals before any 2-removals — so the first level that contains any valid string holds every minimum-removal answer.
Run checks all cases above. Submit evaluates all test cases.