Given a string input_str consisting of lowercase English letters and parentheses ( and ), remove the minimum number of invalid parentheses to produce all possible valid strings. A valid string is one where parentheses are balanced and properly nested. Return a list of unique valid strings with the minimum number of removals. The order of the output strings does not matter.
Example 1
Input: ((a)b)())c(
Output: [((a)b)c,((ab))c,((a)b)()c]
Explanation: All valid strings with minimum removals are listed.
Example 2
Input: abc)(
Output: [abc]
Explanation: Removing both parentheses yields the only valid string.
Example 3
Input: ((x)())y)z(
Output: [((x)())yz,((x)())y(z,((x)())y)z]
Explanation: Multiple valid strings with minimum removals.
Constraints
Case 1
Input: 'a(b)c)d('
Expected: ['a(b)cd','ab(c)d','a(b)cd']
Case 2
Input: '((p)q)())r('
Expected: ['((p)q)r','((pq))r','((p)q)()r']
Case 3
Input: 'x)('
Expected: ['x']
Case 4
Input: '((m)n)o)p('
Expected: ['((m)n)o','((mn)o','((m)n)o']