Balanced Parentheses with Sequential Left Deletions
Problem statement
You are given a string s containing parentheses and decimal digits. Process its characters from left to right. A parenthesis is retained. When a digit d is reached, remove the digit and delete exactly d of the currently retained parentheses to its left, choosing any such positions.
Return true if some sequence of choices leaves a balanced parenthesis string after every character has been processed. Each digit is applied separately; digits are never combined. If fewer than d parentheses are currently retained, that choice is impossible. The empty string is balanced.
Function
canMakeBalanced(s: String) → booleanExamples
Example 1
s = "(()1"return = trueDeleting either one of the first two opening parentheses leaves ().
Example 2
s = "((1))"return = falseAfter deleting one opening parenthesis, two closing parentheses remain.
Example 3
s = "()0"return = trueThe digit zero removes nothing, leaving ().
Constraints
1 ≤ s.length ≤ 16.- Every character of
sis(,), or a digit from0through9. - Each digit deletes exactly its own value from the retained parentheses to its left.