111. Minimum Add to Make Parentheses Valid

🔗 LeetCode Problem: 921. Minimum Add to Make Parentheses Valid
📊 Difficulty: Medium
🏷️ Topics: Stack, String, Greedy

Problem Statement

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.

Return the minimum number of moves required to make s valid.

Example 1:

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

Example 2:

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

Example 3:

Input: s = "()"
Output: 0

Example 4:

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

Constraints: - 1 <= s.length <= 1000 - s[i] is either '(' or ')'.

🌟 ELI5: The Simple Idea!

Think of it like a balance scale:

'(' adds weight to left side   → Need ')' to balance
')' adds weight to right side  → Need '(' to balance

Valid string: Both sides balanced

Example: "()"
  '(' → Left side has 1
  ')' → Right side has 1
  Balanced! ✓

Example: "())"
  '(' → Left: 1
  ')' → Right: 1, balanced so far
  ')' → Right: 1 extra! Need one '(' to balance

Answer: 1

The Core Insight:

Track TWO things:

1. Unmatched '(' (left parentheses waiting for ')')
2. Unmatched ')' (right parentheses with no '(' before them)

Total additions needed = Both counts added together!

🎨 Visual Understanding

Example 1: "())"

Input: "())"

Character by character:
  '(' → One '(' waiting for match
        openCount = 1

  ')' → Matches the waiting '('
        openCount = 0

  ')' → No '(' to match! This ')' is unmatched
        closeCount = 1

Result: 0 unmatched '(' + 1 unmatched ')' = 1

Visualization:
  Original:  ( ) )
  Add:      ^     
  Fixed:    (( ) )  ✓

Example 2: "((("

Input: "((("

Character by character:
  '(' → openCount = 1
  '(' → openCount = 2
  '(' → openCount = 3

Result: 3 unmatched '(' + 0 unmatched ')' = 3

Visualization:
  Original:  ( ( (
  Add:           ) ) )
  Fixed:    ( ( ( ) ) )  ✓

Example 3: "()))(("

Input: "()))(("

Let's trace carefully:

Index 0: '('
  Action: Found opening, waiting for match
  openCount = 1, closeCount = 0

Index 1: ')'
  Action: Found closing, matches with waiting '('
  openCount = 0, closeCount = 0

Index 2: ')'
  Action: Found closing, but no '(' waiting!
  openCount = 0, closeCount = 1

Index 3: ')'
  Action: Found closing, but no '(' waiting!
  openCount = 0, closeCount = 2

Index 4: '('
  Action: Found opening, waiting for match
  openCount = 1, closeCount = 2

Index 5: '('
  Action: Found opening, waiting for match
  openCount = 2, closeCount = 2

Result: 2 unmatched '(' + 2 unmatched ')' = 4

Visualization:
  Original:    ( )  )  )  (  (
  Position:    0 1  2  3  4  5

  Problems:
    - Index 2,3: ')' ')' need '(' before them → add 2 '('
    - Index 4,5: '(' '(' need ')' after them  → add 2 ')'

  One solution: "(())()(())"
    Add '(' before index 2
    Add '(' before index 3  
    Add ')' after index 5
    Add ')' after index 5

🎯 Approach 1: Counter Method (Optimal) ⭐⭐⭐

The Clearest Solution

Algorithm:

Use TWO counters:

openCount: Counts unmatched '(' 
  - Increment when we see '('
  - Decrement when we see ')' and openCount > 0

closeCount: Counts unmatched ')'
  - Increment when we see ')' and openCount == 0

Why this works:
  - If we have waiting '(', a ')' can match it
  - If we don't have waiting '(', the ')' is unmatched
  - At the end, both types of unmatched need additions

Implementation

/**
 * Two-counter approach
 * Time: O(n), Space: O(1)
 */
public int minAddToMakeValid(String s) {
    int openCount = 0;    // Unmatched '(' so far
    int closeCount = 0;   // Unmatched ')' so far

    for (char ch : s.toCharArray()) {
        if (ch == '(') {
            // Found opening bracket - will need matching ')'
            openCount++;
        } else {
            // Found closing bracket ')'
            if (openCount > 0) {
                // Can match with a waiting '('
                openCount--;
            } else {
                // No '(' to match with - this ')' is unmatched
                closeCount++;
            }
        }
    }

    // Total additions = unmatched '(' + unmatched ')'
    return openCount + closeCount;
}

⏰ Time: O(n) - Single pass
💾 Space: O(1) - Only two counters

🔍 Super Detailed Dry Run

Example: s = "()))(("

Goal: Count minimum additions to make valid

═══════════════════════════════════════════════════════════════
Initialization
═══════════════════════════════════════════════════════════════

openCount = 0    (unmatched '(' count)
closeCount = 0   (unmatched ')' count)

s = "()))(("

Think: 
  openCount = How many '(' are waiting for ')'
  closeCount = How many ')' appeared with no '(' before them

═══════════════════════════════════════════════════════════════
Iteration 1: ch = '(' (index 0)
═══════════════════════════════════════════════════════════════

Check: ch == '('? Yes

Action: Increment openCount
  openCount = 0 + 1 = 1

State:
  openCount: 1    (one '(' waiting for match)
  closeCount: 0

Meaning: "I have one '(' that needs a ')' later"

═══════════════════════════════════════════════════════════════
Iteration 2: ch = ')' (index 1)
═══════════════════════════════════════════════════════════════

Check: ch == ')'? Yes
Check: openCount > 0? Yes (openCount = 1)

Action: Match with waiting '('
  openCount = 1 - 1 = 0

State:
  openCount: 0    (all '(' matched so far)
  closeCount: 0

Meaning: 
  "The ')' matched with the '(' from index 0"
  "So far: '()' is balanced ✓"

═══════════════════════════════════════════════════════════════
Iteration 3: ch = ')' (index 2)
═══════════════════════════════════════════════════════════════

Check: ch == ')'? Yes
Check: openCount > 0? No (openCount = 0)

Action: No '(' to match with!
  closeCount = 0 + 1 = 1

State:
  openCount: 0
  closeCount: 1   (one ')' has no '(' before it)

Meaning:
  "This ')' has no matching '(' before it"
  "We'll need to ADD a '(' for this ')'"

═══════════════════════════════════════════════════════════════
Iteration 4: ch = ')' (index 3)
═══════════════════════════════════════════════════════════════

Check: ch == ')'? Yes
Check: openCount > 0? No (openCount = 0)

Action: No '(' to match with!
  closeCount = 1 + 1 = 2

State:
  openCount: 0
  closeCount: 2   (two ')' have no '(' before them)

Meaning:
  "Another ')' with no matching '('"
  "We'll need to ADD another '(' for this ')'"

═══════════════════════════════════════════════════════════════
Iteration 5: ch = '(' (index 4)
═══════════════════════════════════════════════════════════════

Check: ch == '('? Yes

Action: Increment openCount
  openCount = 0 + 1 = 1

State:
  openCount: 1    (one '(' waiting)
  closeCount: 2

Meaning:
  "Found a '(' that will need a ')' later"
  "Still have 2 unmatched ')' from earlier"

═══════════════════════════════════════════════════════════════
Iteration 6: ch = '(' (index 5)
═══════════════════════════════════════════════════════════════

Check: ch == '('? Yes

Action: Increment openCount
  openCount = 1 + 1 = 2

State:
  openCount: 2    (two '(' waiting)
  closeCount: 2

Meaning:
  "Found another '(' that will need a ')' later"
  "Now have 2 unmatched '(' and 2 unmatched ')'"

═══════════════════════════════════════════════════════════════
Final Calculation
═══════════════════════════════════════════════════════════════

Result: openCount + closeCount
Result: 2 + 2 = 4

Breakdown:
  openCount = 2: 
    - The '(' at index 4 needs a ')'
    - The '(' at index 5 needs a ')'
    → Need to ADD 2 closing brackets

  closeCount = 2:
    - The ')' at index 2 needs a '('
    - The ')' at index 3 needs a '('
    → Need to ADD 2 opening brackets

Total additions needed: 4 ✓

Visual representation:
  Original:  ( )  )  )  (  (
             0 1  2  3  4  5
             ↑ ↑  ↑  ↑  ↑  ↑
          match  need  need
                  '('  ')'

  After adding 4 brackets:
    Add '(' before index 2
    Add '(' before index 3
    Add ')' after index 5
    Add ')' after index 5

Another Example: s = "())"

Iteration 1: '('
  openCount = 1, closeCount = 0

Iteration 2: ')'
  openCount > 0? Yes
  openCount = 0, closeCount = 0
  (Matched!)

Iteration 3: ')'
  openCount > 0? No
  openCount = 0, closeCount = 1
  (Unmatched!)

Result: 0 + 1 = 1 ✓

🎯 Approach 2: Stack Method (For Understanding)

Using Stack to Visualize

/**
 * Stack approach - more intuitive but uses more space
 * Time: O(n), Space: O(n)
 */
public int minAddToMakeValid(String s) {
    Stack<Character> stack = new Stack<>();

    for (char ch : s.toCharArray()) {
        if (ch == '(') {
            // Always push opening bracket
            stack.push('(');
        } else {
            // Found closing bracket ')'
            if (!stack.isEmpty() && stack.peek() == '(') {
                // Found a match! Remove the '('
                stack.pop();
            } else {
                // No matching '(' - keep this unmatched ')'
                stack.push(')');
            }
        }
    }

    // Stack contains all unmatched parentheses
    return stack.size();
}

How it works:

Example: "()))(("

'(' → Push     stack: ['(']
')' → Match!   stack: []         (pop the '(')
')' → No match stack: [')']      (push unmatched ')')
')' → No match stack: [')', ')'] (push unmatched ')')
'(' → Push     stack: [')', ')', '(']
'(' → Push     stack: [')', ')', '(', '(']

Result: stack.size() = 4 ✓

Why Counter is Better:

Stack: O(n) space
Counter: O(1) space

Both O(n) time, but counter is more space efficient!

🎯 Why This Solution Works

The Counter Logic

Why two separate counters?

Because '(' and ')' have different meanings:

'(' at position i:
  - Needs a ')' somewhere AFTER position i
  - If we see ')' later, they can match
  - If we never see matching ')', it's unmatched

')' at position i:
  - Needs a '(' somewhere BEFORE position i
  - If we have waiting '(' (openCount > 0), match it
  - If no waiting '(', it's immediately unmatched

We can't fix an unmatched ')' by seeing '(' later!
  Wrong: ")(" - still needs 2 additions
  Can't match them because ')' comes first

So we track them separately:
  openCount: '(' waiting for future ')'
  closeCount: ')' that had no '(' before them

Visual Flow

String: "()))(("

As we go left to right:

Position 0: '('
  Status: [one '(' waiting]

Position 1: ')'
  Status: [matched '()']

Position 2: ')'
  Status: [matched '()', one ')' unmatched]
  Can't be fixed by future '('!

Position 3: ')'
  Status: [matched '()', two ')' unmatched]

Position 4: '('
  Status: [matched '()', two ')' unmatched, one '(' waiting]
  This '(' can't fix the earlier ')'!

Position 5: '('
  Status: [matched '()', two ')' unmatched, two '(' waiting]

Final: 2 unmatched ')' + 2 waiting '(' = 4 additions needed

⚠️ Common Mistakes

Mistake 1: Trying to match ')' with future '('

// ❌ WRONG - Can't match backwards!
for (char ch : s.toCharArray()) {
    if (ch == ')') {
        // Looking for '(' anywhere in string
        // This doesn't work!
    }
}

Why wrong:
  ")(" needs 2 additions
  Can't retroactively match '(' with previous ')'

// ✓ CORRECT - Only match with PREVIOUS '('
if (ch == ')') {
    if (openCount > 0) {
        openCount--;  // Match with earlier '('
    } else {
        closeCount++; // No earlier '(' to match
    }
}

Mistake 2: Single counter

// ❌ WRONG - Can't distinguish the two cases!
int balance = 0;
for (char ch : s.toCharArray()) {
    if (ch == '(') balance++;
    else balance--;
}
return Math.abs(balance);  // Wrong!

Example: ")("
  After '(': balance = -1
  After ')': balance = 0
  Returns: 0 ✗ (should be 2!)

// ✓ CORRECT - Two separate counters

Mistake 3: Not checking openCount before decrementing

// ❌ WRONG - Can go negative!
if (ch == ')') {
    openCount--;  // What if openCount is 0?
}

// ✓ CORRECT - Check first
if (ch == ')') {
    if (openCount > 0) {
        openCount--;
    } else {
        closeCount++;
    }
}

Mistake 4: Forgetting openCount at the end

// ❌ WRONG - Only counting unmatched ')'
return closeCount;

Example: "((("
  Returns: 0 ✗ (should be 3!)

// ✓ CORRECT - Add both
return openCount + closeCount;

🎯 Pattern Recognition

Problem Type: Parentheses Balancing
Core Pattern: Stack Pattern 1 - Matching Pairs (Optimized)

When to Apply:
✓ Matching bracket problems
✓ Need minimum additions/deletions
✓ Don't need actual positions
✓ Can use counter instead of stack

Recognition Keywords:
- "minimum add"
- "make valid"
- "parentheses"
- "moves required"

Similar Problems:
- Valid Parentheses (LC 20) - Check validity
- Generate Parentheses (LC 22) - Generate all
- Remove Invalid Parentheses (LC 301) - Remove minimum
- Longest Valid Parentheses (LC 32) - Find longest

Key Components:
┌────────────────────────────────────────────┐
│ Two counters: open + close               │
│ Open: unmatched '(' waiting              │
│ Close: unmatched ')' with no '(' before  │
│ Match when possible                      │
│ Count both types at end                  │
│ Time: O(n), Space: O(1) optimal!        │
└────────────────────────────────────────────┘

🧠 Interview Strategy

Step 1: "This is minimum additions for valid parentheses"
Step 2: "I'll use two counters to track unmatched brackets"
Step 3: "Process left to right, match when possible"

Key Points to Mention:
- Two counters: openCount and closeCount
- openCount: '(' waiting for ')'
- closeCount: ')' with no '(' before them
- On '(': increment openCount
- On ')': if openCount > 0, match; else increment closeCount
- Result: sum of both counters
- Can't match ')' with future '(' - that's why we track separately

Walk Through Example:
"For '()))((': 
 '(' → openCount=1
 ')' → Match, openCount=0
 ')' → No match, closeCount=1
 ')' → No match, closeCount=2
 '(' → openCount=1, closeCount=2
 '(' → openCount=2, closeCount=2
 Result: 2+2=4"

Why Not Single Counter:
"A single balance counter can't distinguish between
 ')(' (needs 2) and '()' (needs 0). We need to track
 unmatched ')' separately because they can't be fixed
 by future '('."

Space Optimization:
"Could use stack with O(n) space, but two counters
 achieve O(1) space. Both O(n) time."

Complexity:
"O(n) time - single pass. O(1) space - two counters."

📝 Quick Revision Notes

🎯 Core Concept:

Minimum Add Parentheses: Use two counters. openCount tracks unmatched '(' (waiting for ')'). closeCount tracks unmatched ')' (no '(' before them). On '(': openCount++. On ')': if openCount > 0 then openCount-- (match), else closeCount++ (unmatched). Return openCount + closeCount.

⚡ Quick Implementation:

class Solution {
  public int minAddToMakeValid(String s) {
    int open = 0; // increase if ( comes. Decrease if ) comes (only if > 0)
    int close = 0; // increase if ) comes (only if open <= 0)

    for(char ch : s.toCharArray()) {
      switch (ch) {
        case '(':
          open++;
          break;
        default:
          if(open > 0) {
            open--;
          } else {
            close++;
          }
          break;
      }
    }

    return open + close;
  }

  public static void main(String[] args) {
    Solution s = new Solution();
    System.out.println(s.minAddToMakeValid("())") == 1);
    System.out.println(s.minAddToMakeValid("(((") == 3);
    System.out.println(s.minAddToMakeValid("()") == 0);
    System.out.println(s.minAddToMakeValid("()))((") == 4);
  }
}

🔑 Key Insights:

Pattern: Stack Pattern 1 (Matching Pairs - Optimized)
Two types: Unmatched '(' vs unmatched ')'
Can't match backwards: ')' can't match future '('
openCount: '(' needing ')'
closeCount: ')' with no '(' before
Match condition: openCount > 0
Space optimization: O(n) stack → O(1) counters
Time: O(n), Space: O(1) optimal! ✓

🎪 Memory Aid:

"Two counters: left waiting, right unmatched!"
"Match when possible, count both types!" ✨

⚠️ Critical Logic:

On ')':
  if (openCount > 0) → Match!
    openCount--
  else → Unmatched!
    closeCount++

Why? 
  ')' needs '(' BEFORE it
  If we have waiting '(', match
  If not, this ')' is permanently unmatched

Can't fix with future '('!

🧪 Edge Cases

Case 1: All matched

Input: "()"
Output: 0

Case 2: All opening

Input: "((("
Output: 3
openCount=3, closeCount=0

Case 3: All closing

Input: ")))"
Output: 3
openCount=0, closeCount=3

Case 4: Mixed unmatched

Input: "()))(("
Output: 4
openCount=2, closeCount=2

Case 5: Reversed pair

Input: ")("
Output: 2
closeCount=1 first, then openCount=1

All handled correctly! ✓

🎓 Complexity Analysis

Time Complexity: O(n)

Single pass through string: O(n)
Per character: O(1) operations

Example: "()))((" (n=6)
  6 iterations × O(1) = O(n)

Must examine each character once

Space Complexity: O(1)

Only 2 integer variables:
  openCount: O(1)
  closeCount: O(1)

No data structures that grow with input

Compare to stack approach: O(n) space
This is optimal! ✓

Same Pattern: - Valid Parentheses (LC 20) - Generate Parentheses (LC 22) - Remove Invalid Parentheses (LC 301)

Similar Counting: - Score of Parentheses (LC 856) - Minimum Remove to Make Valid (LC 1249)

Advanced: - Longest Valid Parentheses (LC 32) - Valid Parenthesis String (LC 678)

Happy practicing! 🎯

Note: This problem teaches space optimization! The stack approach (O(n) space) can be optimized to two counters (O(1) space). The key insight: track unmatched '(' and ')' separately because ')' can't match with future '('. This pattern of counter optimization appears in many problems! 💪✨