The O(n) Club: Parentheses on the Brink—How to Fix Invalid Parentheses Without Deleting Your Soul

The O(n) Club: Parentheses on the Brink—How to Fix Invalid Parentheses Without Deleting Your Soul

⚡ TL;DR

You’ve been handed a string that thinks it’s a circus act: parentheses swinging everywhere but never quite sticking the landing. Your job: remove as few ( and ) as possible, leave the non-parenthesis characters alone (they’re just extras), and give your interviewer every minimal fix, not just the one you like best.
Good news: brute-force works. Bad news: so does a sledgehammer for removing a lightbulb.
(Here’s what NOT to do:)

// Don't actually use this—it will melt your CPU!
// For every combination of removals, check if the string is valid.
// O(2^n): Burnt laptops, angry managers.
  

🧠 How Devs Usually Mess This Up

🔍 What’s Actually Going On

If you’ve ever played Jenga, you know the goal is to touch as few blocks as possible while keeping the whole thing standing. Removing parentheses is like that, except you need to enumerate every Jenga tower that hasn’t collapsed. Each non-parenthesis char is just a block glued down—don’t even think about removing it.

Optimal strategies use DFS with pruning, BFS for minimal removals, and sets to avoid repeating the most useless thing in programming: duplicate work.

🛠️ PseudoCode

• Step 1: Count your crimes (removals)

  int left = 0, right = 0;
  for (char ch : s.toCharArray()) {
    if (ch == '(') left++;
    else if (ch == ')') {
      if (left > 0) left--;
      else right++;
    }
  }
  // Now, left = number of '(' to remove, right = number of ')' to remove

  Count the exact number of stray left/right parens that MUST go. Otherwise, you’re just rearranging deck chairs on the Titanic.

• Step 2: Backtrack like you mean it (DFS)

  // For every position, if it’s a paren and you still have some quota to remove,
  // try removing it, recurse, and skip dupe states via a Set.

  Only explore unique strings—duplicates are for reality TV, not algorithms.

• Step 3: Judge the survivors

  // Check if string is still balanced (count goes up for '('; down for ')'; never negative)

  Only collect strings where you spent your exact removal budget and thread the parentheses needle perfectly.

💻 The Code

import java.util.*;
 public class ParenthesisRemover {
    public List
<string> removeInvalidParentheses(String s) {
        Set
<string> results = new HashSet<>();
        int[] toRemove = getRemovals(s);
        dfs(s, 0, toRemove[0], toRemove[1], results, new HashSet<>());
        return new ArrayList<>(results);
    }
     private int[] getRemovals(String s) {
        int left = 0, right = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') left++;
            else if (c == ')') {
                if (left > 0) left--;
                else right++;
            }
        }
        return new int[]{left, right};
    }
     private void dfs(String s, int start, int leftRem, int rightRem, Set
<string> results, Set<string> visited) {
        if (leftRem == 0 && rightRem == 0) {
            if (isValid(s)) results.add(s);
            return;
        }
        for (int i = start; i < s.length(); i++) {
            if (i > start && s.charAt(i) == s.charAt(i - 1)) continue;
            char c = s.charAt(i);
            if (c != '(' && c != ')') continue;
            String next = s.substring(0, i) + s.substring(i + 1);
            if (!visited.add(next)) continue;
            if (c == '(' && leftRem > 0) {
                dfs(next, i, leftRem - 1, rightRem, results, visited);
            }
            else if (c == ')' && rightRem > 0) {
                dfs(next, i, leftRem, rightRem - 1, results, visited);
            }
        }
    }
     private boolean isValid(String s) {
        int count = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') count++;
            else if (c == ')') {
                if (count == 0) return false;
                count--;
            }
        }
        return count == 0;
    }
     public static void main(String[] args) {
        ParenthesisRemover remover = new ParenthesisRemover();
        System.out.println(remover.removeInvalidParentheses("()())()"));
        System.out.println(remover.removeInvalidParentheses("(a)())()"));
    }
}</string></string></string></string>

⚠️ Pitfalls, Traps & Runtime Smacks

• Edge Cases Galore: Only right parens, only left parens, totally empty, or the evil “)(” – all covered.
• Set Tracking or Bust: Miss this and your “unique” answers become an infinite group chat.
• Never Delete Regular Characters: Seriously. Keep your hands off the innocent bystanders.
• Complexity: The fate of your CPU can be O(2^n) in the worst case, but tree-pruning keeps it mostly civil for practical strings. (Unless your input is 10,000 parentheses—then, may the GC gods help you.)

🧠 Interviewer Brain-Tattoo

“Returning extra removals is like deleting Slack for every typo: technically thorough, but fundamentally missing the point (and likely to get you fired).”