Loading problem…
A parentheses string is valid if and only if: 1. It is the empty string, 2. It can be written as AB (A concatenated with B), where A and B are valid strings, or 3. It can be written as (A), where A is a valid string. You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string. For example, if s = "()))", you can insert an opening parenthesis to be "(()))" or a closing parenthesis to be "())))". Return the minimum number of moves required to make s valid.
Example 1
Input: s = ())
Output: 1
Explanation: The first two characters pair up, but the final ')' has no opener waiting for it, so one '(' must be inserted to balance it.
Example 2
Input: s = (((
Output: 3
Explanation: Three opening brackets are left without partners, so three closing brackets must be added.
Example 3
Input: s = ()))((
Output: 4
Explanation: Two ')' are stranded with no opener (needing two '(' inserted) and two '(' are left waiting at the end (needing two ')'), for four moves total.
Track how many opening brackets are still waiting for a partner. A closing bracket that arrives with nobody waiting needs an opener inserted; any openers still waiting at the end each need a closer.
Run checks all cases above. Submit evaluates all test cases.