A parentheses string is valid if and only if:
AB
(A
concatenated with B
), where A
and B
are valid strings, or(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
Example 2:
Input: s = "(((" Output: 3
Can you write code to solve the problem?
A brute force approach would involve trying all possible combinations of inserting parentheses to make the string valid. This would be extremely inefficient as the number of combinations grows exponentially with the string length, making it impractical even for moderately sized strings. We'd have to generate all possible strings with added parentheses and then check each one for validity. The validity check would also have to iterate through each char, so the complexity grows very rapidly.
A more efficient approach utilizes a simple counter to keep track of the balance between open and close parentheses. Iterate through the string. If we encounter an open parenthesis, increment the counter. If we encounter a closing parenthesis, check if the counter is greater than zero. If it is, decrement the counter, indicating a match. If it's not, increment a separate counter to keep track of the number of unmatched closing parentheses. After iterating, the sum of the unmatched closing parentheses counter and the remaining open parentheses counter will give the minimum number of moves to make the string valid.
def min_add_to_make_valid(s):
open_count = 0
close_needed = 0
for char in s:
if char == '(': # opening bracket
open_count += 1
elif open_count > 0:
open_count -= 1
else:
close_needed += 1
return open_count + close_needed
# Example usage
s1 = "()))"
print(f'Minimum moves for {s1}: {min_add_to_make_valid(s1)}')
s2 = "((("
print(f'Minimum moves for {s2}: {min_add_to_make_valid(s2)}')
s3 = "()"
print(f'Minimum moves for {s3}: {min_add_to_make_valid(s3)}')
s4 = "()()"
print(f'Minimum moves for {s4}: {min_add_to_make_valid(s4)}')
s5 = "()))(("
print(f'Minimum moves for {s5}: {min_add_to_make_valid(s5)}')
s6 = ""
print(f'Minimum moves for {s6}: {min_add_to_make_valid(s6)}')