Compute Minimum Parentheses Additions

Given a string s consisting only of the characters '(' and ')', compute the minimum number of parentheses that must be inserted anywhere in the string so that the resulting string is a valid parentheses string.

A valid parentheses string is one where every opening parenthesis has a matching closing parenthesis, every closing parenthesis matches a previous unmatched opening parenthesis, and the pairs are properly nested.

Return a single integer: the minimum number of insertions required.

Example:

Input: s = "()))(("
Output: 4

Explain your approach and analyze its time and space complexity.

Minimum Parentheses Additions

Return the minimum number of parentheses insertions needed to make s valid.

Constraints

• s contains only '(' and ')'

Hints

1. Count unmatched closing parentheses and unmatched openings.