659. Remove Invalid Parentheses

Given a string s of parentheses and lowercase letters, remove the minimum number of parentheses to make it valid, and return all distinct valid results in ascending (lexicographic) order. The input is JSON {s}.

Input: JSON {s}.

Output: Array — the distinct valid strings, sorted ascending.

Examples

Input: {"s":"()())()"}
Output: ["(())()","()()()"]
Explanation: Two minimal removals.

Input: {"s":"(a)())()"}
Output: ["(a())()","(a)()()"]
Explanation: Letters are preserved.

Input: {"s":")("}
Output: [""]
Explanation: Everything removable.

Constraints

• 1<=|s|<=25

Asked by