804. Remove Invalid Parentheses — Count Minimum-Removal Solutions

Given s with parens and letters, find the minimum number of parens to remove to make it valid, then return the COUNT of distinct valid strings achievable with that minimum removal. If already valid, return 1.

Input: A quoted string.

Output: Integer count.

Examples

Input: "()())()"
Output: 2
Explanation: Remove index 3 or index 4 -> '()()()' or '(())()'.

Input: ")("
Output: 1
Explanation: Remove both -> ''.

Constraints

• 0 <= s.length <= 20

Asked by