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: ```text Input: s = "()))((" Output: 4 ``` Explain your approach and analyze its time and space complexity.