DSA Tutorial

🔍

Stack Basics Stack Operations Stack Implementation Stack Collection Frameworks Balanced Parentheses Expression Evaluation Monotonic Stack Practice Problems

Queue Basics Queue Operations Queue Implementation Queue Collection Frameworks Circular Queue Deque Priority Queue Queue in BFS Practice Problems

Tree Basics & Terminologies Types of Trees Binary Tree Basics & Types Binary Tree DFS Traversals BFS / Level Order Traversal Binary Tree Operations Binary Tree Practice Problems BST Basics BST DFS Traversals BST BFS Traversal BST Operations BST Practice Problems Heap Trie Advanced Trees

Graph Basics and Terminologies Graph Representation Types of Graphs Breadth First Search (BFS)Depth First Search (DFS)Connected Components Cycle Detection Topological Sort Shortest Path Algorithms Dijkstra's Algorithm Minimum Spanning Tree Union Find (DSU)Practice Problems

Backtracking Basics Decision Tree Thinking Time & Space Complexity Subsets Permutations Combination Problems N-Queens Sudoku Solver Word Search Common Mistakes Practice Problems

DP Basics State Transition Thinking Memoization Tabulation Memoization vs Tabulation 1D Dynamic Programming 2D Dynamic Programming Knapsack Pattern Longest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Time & Space Complexity Common Mistakes Practice Problems

Two Pointers Sliding Window Fast & Slow Pointers Prefix Sum Hashing Pattern Binary Search Pattern Greedy Pattern Divide & Conquer Heap Pattern Monotonic Stack & Queue Practice Problems

Top 100 DSA Problems Blind 75 NeetCode 150 Pattern → Problem Map Easy → Medium Roadmap Medium → Hard Roadmap FAANG Question Bank Mock Interviews

Weekly Revision Plan Spaced Repetition Guide Mixed Problem Sets Mock Interview Schedule Self Assessment Checklist

Balanced Parentheses

Why Balanced Parentheses Is a Core Stack Problem

Balanced parentheses is the canonical introduction to stack-based problem solving. Every variant — checking validity, counting fixes, finding the longest valid window — reduces to the same core mechanic: use LIFO ordering to match the most recently opened bracket with the next closing bracket.

The applications page introduced the basic check. This page covers every interview-relevant variant in depth.

Variants covered:
  1. Basic check      — is the string valid?
  2. Count score      — score a parentheses string
  3. Minimum additions— minimum insertions to make it valid
  4. Wildcards        — '*' can be '(', ')' or ''
  5. Longest valid    — longest valid substring
  6. Remove invalid   — remove fewest brackets to make valid

Variant 1: Basic Validity Check

The foundation. Push every opening bracket, pop and match on every closing bracket. Valid if and only if the stack is empty at the end.

Java

import java.util.Deque;
import java.util.ArrayDeque;

public class BasicCheck {

    public static boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();

        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) return false;
                char top = stack.pop();
                if (c == ')' && top != '(') return false;
                if (c == '}' && top != '{') return false;
                if (c == ']' && top != '[') return false;
            }
        }

        return stack.isEmpty();
    }

    public static void main(String[] args) {
        System.out.println(isValid("()[]{}"));   // true
        System.out.println(isValid("([{}])"));   // true
        System.out.println(isValid("([)]"));     // false — wrong nesting
        System.out.println(isValid("{[]"));      // false — unclosed
        System.out.println(isValid("]"));        // false — no opener
        System.out.println(isValid(""));         // true — empty is valid
    }
}

Output:
true
true
false
false
false
true

Dry Run: `"([{}])"`

char '(':  push '('    stack=['(']
char '[':  push '['    stack=['(', '[']
char '{':  push '{'    stack=['(', '[', '{']
char '}':  top='{' matches '}' → pop  stack=['(', '[']
char ']':  top='[' matches ']' → pop  stack=['(']
char ')':  top='(' matches ')' → pop  stack=[]

Stack empty → return true ✓

Dry Run: `"([)]"` — Why It Fails

char '(':  push '('    stack=['(']
char '[':  push '['    stack=['(', '[']
char ')':  top='[' ≠ '(' → MISMATCH → return false

The brackets are interleaved: ( [ ) ] — closing ) expects (
but finds [ at the top. LIFO correctly rejects cross-nesting.

Variant 2: Score of Parentheses

Problem: Given a balanced parentheses string, compute its score:

›() → 1
›AB → score(A) + score(B)
›(A) → 2 × score(A)

Stack insight: Push 0 as a layer counter. When ( appears, push a new layer. When ) appears, pop the top layer — if it is 0 the closing matched an empty () = 1, otherwise it doubles the inner score and adds to the layer below.

Java

import java.util.Deque;
import java.util.ArrayDeque;

public class ScoreParentheses {

    public static int scoreOfParentheses(String s) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(0);   // Base layer score

        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(0);   // New inner layer
            } else {
                int inner = stack.pop();                    // Inner layer score
                int outer = stack.pop();                    // Layer below
                // () = 1, (A) = 2 * score(A)
                stack.push(outer + Math.max(2 * inner, 1));
            }
        }

        return stack.pop();
    }

    public static void main(String[] args) {
        System.out.println(scoreOfParentheses("()"));         // 1
        System.out.println(scoreOfParentheses("(())"));       // 2
        System.out.println(scoreOfParentheses("()()"));       // 2
        System.out.println(scoreOfParentheses("((()))"));     // 4
        System.out.println(scoreOfParentheses("(()())"));     // 4
        System.out.println(scoreOfParentheses("(()(()))"));   // 6
    }
}

Output:
1
2
2
4
4
6

Dry Run: `"(()())"` → score = 4

stack = [0]

'(':  push 0     stack=[0, 0]
'(':  push 0     stack=[0, 0, 0]
')':  inner=0, outer=0  → outer + max(2*0,1) = 0+1 = 1  → push 1  stack=[0, 1]
'(':  push 0     stack=[0, 1, 0]
')':  inner=0, outer=1  → 1 + max(2*0,1) = 1+1 = 2  → push 2   stack=[0, 2]
')':  inner=2, outer=0  → 0 + max(2*2,1) = 0+4 = 4  → push 4   stack=[4]

Result: 4 ✓

The outer ) sees inner score=2 (from two () inside),
doubles it → 4. The rule: () = 1, (A) = 2 * score(A).

Variant 3: Minimum Additions to Make Valid

Problem: Given a string of ( and ), return the minimum number of brackets to add to make it valid.

Approach: Count unmatched ( and unmatched ) separately. Unmatched ) must have a ( added before them; unmatched ( must have a ) added after them.

Java

public class MinimumAdditions {

    public static int minAddToMakeValid(String s) {
        int openNeeded  = 0;  // Unmatched ')' — need a '(' before them
        int closeNeeded = 0;  // Unmatched '(' — need a ')' after them

        for (char c : s.toCharArray()) {
            if (c == '(') {
                closeNeeded++;       // This '(' is waiting for a ')'
            } else {
                if (closeNeeded > 0) {
                    closeNeeded--;   // Matched with a pending '('
                } else {
                    openNeeded++;    // No '(' to match — need to add one
                }
            }
        }

        // Total additions needed
        return openNeeded + closeNeeded;
    }

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

Output:
1
3
0
4
0

Dry Run: `"()))(("` → answer = 4

openNeeded=0, closeNeeded=0

'(':  closeNeeded=1   (one unmatched open)
')':  closeNeeded>0 → closeNeeded=0  (matched)
')':  closeNeeded=0 → openNeeded=1   (unmatched close — need '(' before)
')':  closeNeeded=0 → openNeeded=2   (another unmatched close)
'(':  closeNeeded=1
'(':  closeNeeded=2

Total: openNeeded=2 (add 2 '(' before unmatched ')')
       closeNeeded=2 (add 2 ')' after unmatched '(')
Answer: 2 + 2 = 4 ✓

Variant 4: Valid Parenthesis String (With Wildcards)

Problem: Given a string with (, ), and * where * can be (, ), or empty string, return true if it can be valid.

Approach: Track a range [lo, hi] of possible unmatched ( counts. lo = minimum possible unmatched (, hi = maximum. If hi < 0 at any point, too many ) — invalid. At the end, check lo == 0 (minimum unmatched opens is 0).

Java

public class WildcardParentheses {

    public static boolean checkValidString(String s) {
        int lo = 0;   // Minimum possible unmatched '('
        int hi = 0;   // Maximum possible unmatched '('

        for (char c : s.toCharArray()) {
            if (c == '(') {
                lo++;   // Must be open
                hi++;
            } else if (c == ')') {
                lo--;   // Might be close — reduce min
                hi--;   // Definitely reduces max
            } else {    // '*'
                lo--;   // If '*' acts as ')' — reduces min
                hi++;   // If '*' acts as '(' — increases max
            }

            // hi < 0: too many ')' — can't be fixed
            if (hi < 0) return false;
            // lo can't go below 0 — unmatched count can't be negative
            lo = Math.max(lo, 0);
        }

        // lo == 0 means it's possible to have 0 unmatched '('
        return lo == 0;
    }

    public static void main(String[] args) {
        System.out.println(checkValidString("()"));      // true
        System.out.println(checkValidString("(*)"));     // true
        System.out.println(checkValidString("(*))"));    // true
        System.out.println(checkValidString("(*))("));   // false
        System.out.println(checkValidString("**"));      // true
        System.out.println(checkValidString(")*("));     // false
    }
}

Output:
true
true
true
false
true
false

Dry Run: `"(*))"`

lo=0, hi=0

'(':  lo=1, hi=1
'*':  lo=0, hi=2   (* can be (, ) or empty → range widens)
')':  lo=-1, hi=1  → lo=max(-1,0)=0, hi=1
')':  lo=-1, hi=0  → lo=max(-1,0)=0, hi=0

hi=0 ≥ 0 → ok
lo=0 → return true ✓

Explanation: "(*))" works as "()" where '*' becomes empty,
or as "(())" where '*' becomes '('.

Variant 5: Longest Valid Parentheses Substring

Problem: Given a string of ( and ), find the length of the longest valid (well-formed) parentheses substring.

Stack approach: Push indices onto the stack. Start with -1 as a base index. When ) closes a (, pop and the current valid length is i - stack.top().

Java

import java.util.Deque;
import java.util.ArrayDeque;

public class LongestValidParentheses {

    public static int longestValidParentheses(String s) {
        Deque<Integer> stack  = new ArrayDeque<>();
        stack.push(-1);    // Base index — anchors the start of valid substrings
        int maxLen = 0;

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);   // Push index of opening bracket
            } else {
                stack.pop();     // Match with top
                if (stack.isEmpty()) {
                    stack.push(i);   // No match — new base index
                } else {
                    // Length from last unmatched index to current
                    maxLen = Math.max(maxLen, i - stack.peek());
                }
            }
        }

        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println(longestValidParentheses("(()"));     // 2
        System.out.println(longestValidParentheses(")()())"));  // 4
        System.out.println(longestValidParentheses(""));        // 0
        System.out.println(longestValidParentheses("()()"));    // 4
        System.out.println(longestValidParentheses("()(()"));   // 2
    }
}

Output:
2
4
0
4
2

Dry Run: `")()())"` → longest = 4

stack=[-1], maxLen=0

i=0 ')': pop -1 → stack=[] → empty → push 0  stack=[0]
i=1 '(': push 1                               stack=[0,1]
i=2 ')': pop 1 → stack=[0] → len=2-0=2  maxLen=2
i=3 '(': push 3                               stack=[0,3]
i=4 ')': pop 3 → stack=[0] → len=4-0=4  maxLen=4
i=5 ')': pop 0 → stack=[] → empty → push 5   stack=[5]

Result: 4 ✓ (substring "()()" from index 1 to 4)

Key insight: the stack always holds the index of the last
unmatched bracket (the left boundary). When a match occurs,
the valid length extends from the new top to the current index.

Variant 6: Remove Invalid Parentheses

Problem: Remove the minimum number of brackets to make the string valid. Return all unique results.

Approach (BFS): Treat each string as a state. Remove one bracket at a time, add to the next level. The first level where a valid string is found contains all minimal-removal answers.

Java

import java.util.*;

public class RemoveInvalidParentheses {

    private static boolean isValid(String s) {
        int count = 0;
        for (char c : s.toCharArray()) {
            if      (c == '(') count++;
            else if (c == ')') { if (--count < 0) return false; }
        }
        return count == 0;
    }

    public static List<String> removeInvalidParentheses(String s) {
        List<String>   result  = new ArrayList<>();
        Set<String>    visited = new HashSet<>();
        Queue<String>  queue   = new LinkedList<>();

        queue.offer(s);
        visited.add(s);
        boolean found = false;   // Found valid strings at this removal level

        while (!queue.isEmpty()) {
            String curr = queue.poll();

            if (isValid(curr)) {
                result.add(curr);
                found = true;
            }

            // Once a valid string is found at this level, stop generating
            if (found) continue;

            // Generate all strings with one bracket removed
            for (int i = 0; i < curr.length(); i++) {
                if (curr.charAt(i) != '(' && curr.charAt(i) != ')') continue;

                String next = curr.substring(0, i) + curr.substring(i + 1);
                if (visited.add(next)) {
                    queue.offer(next);
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {
        System.out.println(removeInvalidParentheses("()())()"));
        // ["(())()", "()()()"]
        System.out.println(removeInvalidParentheses("(a)())()"));
        // ["(a())()", "(a)()()"]
        System.out.println(removeInvalidParentheses(")(")); 
        // [""]
    }
}

Output:
["(())()", "()()()"]
["(a())()", "(a)()()"]
[""]

Pattern Recognition Guide

All six variants share the same core mechanic but ask different questions:

Question                              | Variant      | Technique
──────────────────────────────────────────────────────────────────
Is the string valid?                  | Basic check  | push/pop + isEmpty()
What is its score?                    | Score        | layer counter on stack
How many additions to make it valid?  | Min add      | two counters: open/close
Is it valid with wildcards?           | Wildcards    | range [lo, hi] tracking
What is the longest valid substring?  | Longest      | index stack + base -1
Minimum removals to make valid?       | Remove min   | BFS level by level

Time and Space Complexity

Variant	Time	Space	Notes
Basic validity	O(n)	O(n)	Stack holds at most n/2 chars
Score	O(n)	O(n)	Stack depth = nesting depth
Min additions	O(n)	O(1)	Two integer counters only
Wildcards (range)	O(n)	O(1)	lo and hi only
Longest valid	O(n)	O(n)	Index stack
Remove invalid (BFS)	O(n × 2ⁿ)	O(n × 2ⁿ)	Exponential — all subsets

Common Mistakes

Not resetting lo to 0 in the wildcard variant. lo tracks the minimum possible unmatched (. It can never go negative — a count of -1 unmatched opens is meaningless. Always apply lo = max(lo, 0) after decrementing. Without this, lo < 0 causes false negatives — valid strings reported as invalid.

Forgetting the base index -1 in longest valid substring. The -1 anchors the start. When the very first valid pair is found, i - stack.top() = i - (-1) = i + 1 = correct length. Without -1, the first valid pair has an empty stack, and the length calculation has nothing to subtract from.

Not checking stack.isEmpty() before pop in basic validity. A ) with an empty stack means an unmatched closing bracket — the string is invalid. Popping an empty stack throws an exception. The empty check and immediate false return must come before stack.pop().

Using queue.poll() result without checking found before generating children in remove-invalid BFS. Once a valid string at minimum removal depth is found, all strings at this BFS level should be collected, but no deeper strings should be enqueued. The found flag prevents exploring unnecessary deeper levels.

Wrong counter in min additions. Unmatched ) require a ( to be added before them — tracked by openNeeded. Unmatched ( require a ) to be added after them — tracked by closeNeeded. Swapping these counts gives the wrong answer on asymmetric inputs.

Interview Questions

Q: Why is a stack the natural structure for bracket matching?

Brackets form a nested structure — the most recently opened bracket must be the first one closed. This is exactly LIFO ordering. A stack always gives O(1) access to the most recently pushed element, which is the most recently opened bracket. Any other structure (queue, array with linear scan) would require O(n) to find the matching opener, turning the overall algorithm from O(n) to O(n²).

Q: How does the index-based stack for longest valid parentheses differ from the character-based stack for basic validity?

Basic validity pushes characters (or just tracks a count). Longest valid parentheses pushes indices so it can compute substring lengths. When a match occurs, i - stack.top() gives the length of the current valid run. The base index -1 acts as a left boundary anchor — without it, the first valid pair would have an empty stack and no length to compute. The index approach works because each valid pair extends from the last unmatched position to the current index.

Q: What is the time complexity of remove-invalid-parentheses and why?

O(n × 2ⁿ) in the worst case. At each BFS level, we generate all possible single-character removals — up to n strings of length n-1. Each string is hashed and stored. In the worst case, we remove n characters before finding a valid string. Total: n levels × n removals × n characters = O(n³), bounded by O(n × 2ⁿ) for the number of unique subsets. This is acceptable because the problem's output itself can be exponential in the worst case (exponentially many valid answers).

FAQs

Can the min-additions approach be solved without a stack?

Yes — the two-counter approach uses O(1) space (no stack). Track openNeeded (unmatched )) and closeNeeded (unmatched (). This is effectively simulating what the stack would track but condensing it to two integers. The two-counter approach only works because ( and ) are always added in symmetrical pairs, making the count sufficient. Multi-type brackets (like {, [) require the stack to track which type is open.

What does lo == 0 mean at the end of the wildcard check?

lo is the minimum possible count of unmatched ( given all the wildcard choices. If lo > 0, there are at least lo unmatched opens that cannot be closed regardless of how wildcards are assigned. lo == 0 means there exists at least one assignment of wildcards that results in zero unmatched opens — so the string is potentially valid.

Is there a faster approach for remove-invalid-parentheses than BFS?

Yes — first compute the minimum number of removals needed using the two-counter method. Then use DFS with pruning: recurse, skipping brackets that would be removed, and deduplicate using a set. This avoids generating all BFS levels but has the same worst-case complexity. Both BFS and DFS produce all unique results with minimum removals; BFS is generally more intuitive for this problem.

Quick Quiz

Question 1: "([)]" fails the basic validity check. At which character does the failure occur?

›A) The [ — brackets cannot be mixed
›B) The ) — stack top is [ but ) expects (
›C) The ] — stack is empty when ] arrives
›D) The end — stack is non-empty

Answer: B) The ) — mismatch at the third character. After pushing ( and [, the closing ) checks the top of the stack and finds [. Since [ ≠ (, the match fails immediately and false is returned.

Question 2: For min_add_to_make_valid("()))(("), the answer is 4. Which 4 brackets need to be added?

›A) Two ( at the start and two ) at the end
›B) Two ( before the unmatched ) and two ) after the unmatched (
›C) Four ) at the end
›D) One ( and three )

Answer: B) Two ( before the unmatched ) and two ) after the unmatched (. openNeeded = 2 (two ) appear without a matching ( — need to add 2 ( before them). closeNeeded = 2 (two ( at the end have no ) — need to add 2 ) after them). Total: 2 + 2 = 4.

Question 3: In longest valid parentheses, what does the base index -1 in the stack represent?

›A) An error sentinel — indicates invalid state
›B) The left boundary before the string starts — anchors length calculation
›C) A dummy opening bracket at position -1
›D) Nothing — it can be replaced with 0

Answer: B) Left boundary anchor. When the first valid pair () is matched at index 1, i - stack.top() = 1 - (-1) = 2 — correct length. Without -1, popping the ( at index 0 leaves an empty stack, making length computation impossible for the first valid pair.

Question 4: In the wildcard variant "(*)", what are the [lo, hi] ranges after processing each character?

›A) [1,1], [0,2], [-1,1] → lo reset → [0,1] → return lo==0
›B) [1,1], [0,2], [0,0] → return true
›C) [0,0], [0,2], [0,0] → return true
›D) [1,1], [1,2], [0,1] → return lo==0

Answer: A) [1,1] → [0,2] → [lo reset to 0, 1] → lo==0. After (: lo=1, hi=1. After *: lo=0, hi=2. After ): lo=-1, hi=1 → reset lo to 0. Final: lo=0 → return true. The * widens the possible range — lo decreases (if * = )) and hi increases (if * = ().

Summary

Balanced parentheses problems form a family — each variant builds on the same core: LIFO ordering ensures the most recently opened bracket is closed first.

Six variants with their key techniques:

›Basic validity — push openers, pop and match closers, valid iff stack empty
›Score — layer counter stack, () = 1, (A) = 2 × score(A), max(2*inner, 1) handles both
›Min additions — two counters: openNeeded for unmatched ), closeNeeded for unmatched (
›Wildcards — range [lo, hi] of possible unmatched opens, lo = max(lo,0) prevents negatives, return lo == 0
›Longest valid — index stack with base -1, length = i - stack.top() after each match
›Remove invalid — BFS level by level, stop at first level with valid strings, deduplicate with Set

Complexity ranges from O(n) time O(1) space (min additions, wildcards) to O(n × 2ⁿ) (remove invalid). The index-based stack for longest valid is O(n) time O(n) space and the most technically subtle variant.

←

PreviousStack Collection Frameworks

NextExpression Evaluation

→

Balanced Parentheses

Why Balanced Parentheses Is a Core Stack Problem

Variant 1: Basic Validity Check

Dry Run: "([{}])"

Dry Run: "([)]" — Why It Fails

Variant 2: Score of Parentheses

Dry Run: "(()())" → score = 4

Variant 3: Minimum Additions to Make Valid

Dry Run: "()))((" → answer = 4

Variant 4: Valid Parenthesis String (With Wildcards)

Dry Run: "(*))"

Variant 5: Longest Valid Parentheses Substring

Dry Run: ")()())" → longest = 4

Variant 6: Remove Invalid Parentheses

Pattern Recognition Guide

Time and Space Complexity

Common Mistakes

Interview Questions

FAQs

Quick Quiz

Summary

Dry Run: `"([{}])"`

Dry Run: `"([)]"` — Why It Fails

Dry Run: `"(()())"` → score = 4

Dry Run: `"()))(("` → answer = 4

Dry Run: `"(*))"`

Dry Run: `")()())"` → longest = 4