FastPrep

Description

Solutions

Minimum Insertions to Balance a Parentheses String

🔥 FULLTIME📚RELATED PROBLEMS

Given a string that consists of left and right parentheses, '(' and ')', balance the parentheses by inserting parentheses as necessary. Determine the minimum number of characters that must be inserted.

Function Description

Complete the function minInsertionsToBalance in the editor.

minInsertionsToBalance has the following parameter:

String s: the initial parentheses sequence

Returns

int: the minimum number of insertions

Example 1:

Input:  s = "()))"
Output: 2 
Explanation:
N/A

Example 2:

Input:  s = "(()))"
Output: 4 
Explanation:
      Insert 1 left parenthesis at the left end of the string to get '((()))'. The string is balanced after 1 insertion.

      s = '))(('
      Insert 2 left parentheses at the start and 2 right parentheses at the end of the string 
      to get "(())(())" after 4 insertions.

Constraints:

1 ≤ length of s ≤ 10⁵