Problem

A parentheses string is valid if and only if:

  • It is the empty string,
  • It can be written as AB (A concatenated with B), where A and B are valid strings, or
  • It can be written as (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.

Examples

Example 1:

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

Example 2:

Input: s = "((("
Output: 3

Solution

Video explanation

Here is the video explaining below methods in detail. Please check it out:

Method 1 - Using Stack

Loop through the input array, and initialize the stack and left counter signifying number of left parenthesis required:.

  1. If we encounter ‘(’, push ‘(’ into stack;
  2. otherwise, ‘)’, check if there is a matching ‘(’ on top of stack; if no, increase the left counter by 1; if yes, pop it out;
  3. after the loop, count in the un-matched characters remaining in the stack.

Code

Java
public class Solution {
    public int minAddToMakeValid(String s) {
        // Initialize a stack to keep track of unmatched opening parentheses
        Deque<Character> stk = new ArrayDeque<>();
        
        // Initialize a counter to count the unmatched closing parentheses
        int left = 0;
        
        // Traverse each character in the string
        for (char ch : s.toCharArray()) {
            if (ch == '(') {
                // If it's an opening parenthesis, push it onto the stack
                stk.push(ch);
            } else if (!stk.isEmpty()) {
                // If it's a closing parenthesis and there's a matching opening parenthesis in the stack, pop the stack
                stk.pop();
            } else {
                // If it's a closing parenthesis with no matching opening parenthesis, increment the left counter
                left++;
            }
        }
        
        // The total needed moves to make the string valid are the sum of the unmatched closing parentheses (left)
        // and the unmatched opening parentheses (remaining elements in the stack)
        return left + stk.size();
    }
}
Python
 class Solution:
     def minAddToMakeValid(self, s: str) -> int:
         stack = []
         left = 0
         for ch in s:
             if ch == '(':
                 stack.append(ch)
             elif stack:
                 stack.pop()
             else:
                 left += 1
         return left + len(stack)

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string s, because we process each character exactly once.
  • 🧺 Space complexity: O(n)

Method 2 - Track left and right bracket needed

Here is the approach:

  1. Understanding Valid Parentheses:

    • A valid parentheses string must balance every opening parenthesis '(' with a closing parenthesis ')'.

  2. Count Imbalance:

    • Traverse the string s, maintaining a count of open and close braces.
    • An imbalance occurs when there are more closing parentheses ')' than opening parentheses '(' at any point.

  3. Calculate Minimum Moves:

    • Use a counter to track the number of moves to balance open and close parentheses.
    • As you traverse the string:
      • If a mismatch is detected (more ')' than '('), increment the counter.
      • At the end of traversal, the count of unbalanced opening parentheses also needs to be accounted for in the result.

Code

Java
public class Solution {
    public int minAddToMakeValid(String s) {
        int left = 0;  // Track needed opening parentheses
        int right = 0; // Track needed closing parentheses
        
        for (char ch : s.toCharArray()) {
            if (ch == '(') {
                right++;  // Increase closing parenthesis needed
            } else if (right > 0) {
                right--;  // One closing parenthesis matched
            } else {
                left++;  // Extra closing parenthesis found
            }
            
        }
        
        // Total needed valid moves are the sum of left and right
        return left + right;
    }
}
Python
class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        left = 0  # Track needed opening parentheses
        right = 0 # Track needed closing parentheses
        
        for char in s:
            if char == '(':
                right += 1  # Increase closing parenthesis needed
            elif right > 0:
                right -= 1  # One closing parenthesis matched
            else:
                left += 1  # Extra closing parenthesis found
        
        # Total needed valid moves are the sum of left and right
        return left + right

Complexity

  • ⏰ Time complexity: O(n), because we process each character exactly once.
  • 🧺 Space complexity: O(1)- , since we use a few additional variables to keep track of the counters for the needed parentheses, and no additional data structures are used.