5 LeetCode Parentheses problems: patterns, approaches, and key lessons

These five problems all involve parentheses, but they require different ways of thinking algorithmically. Similar input symbols do not necessarily imply the same algorithm.


The key question is: What information must we preserve to make the next correct decision?


Overview

20. Valid Parentheses - Stack for tracking nesting order
22. Generate Parentheses - Backtracking + pruning for constructing only valid candidates
32. Longest Valid Parentheses - Stack + indices for tracking boundaries of valid substrings
678. Valid Parenthesis String - Greedy + range tracking for representing multiple possible states compactly
1190. Reverse Substrings Between Each Pair of Parentheses - Stack / pair mapping - for processing nested operations efficiently


20. Valid Parentheses

Pattern: Stack (LIFO)

Goal: Determine whether brackets of three types - (), {}, and [] - are correctly matched and nested.

Example: {[()]} is valid, while ([)] is not.


Why a stack?

Brackets close in the reverse order of their opening. This is LIFO (Last In, First Out).


For {[()]}:


  1. Read {: push it.
  2. Read [: push it.
  3. Read (: push it.
  4. Read ): match and pop (.
  5. Read ]: match and pop [.
  6. Read }: match and pop {.

Why not just use counters?

Counters track quantities, not order. ([)] has matching counts for every bracket type, but the nesting is invalid. A stack preserves the order that matters.


Complexity:
Time O(n) and space O(n) in the worst case.


What should remember: Recognize problems where the current element must interact with the most recently opened, unfinished element. This idea appears in parsing, nested structures, HTML/XML validation, and expression processing.



22. Generate Parentheses

Pattern: Backtracking + pruning

Goal: Generate all valid combinations of n pairs of parentheses.


For n = 3, the results are:

((()))
(()())
(())()
()(())
()()()

Why backtracking?

Unlike Problem 20, we are not validating an existing string. We are constructing strings step by step.

At each step, we can append ( or ), but only under these conditions:

  • Append ( if open < n.
  • Append ) if close < open.

For n = 2, the valid branches are:

start
  └── (
      ├── ((
      │   └── (():
      │       └── (())
      └── ()
          └── ()(
              └── ()()

Each prefix must remain capable of becoming a valid result.


Why not generate every string and validate afterward?

There are 22n = 4n binary choices of ( or ) for a string of length 2n, and most are invalid. Backtracking with pruning avoids exploring branches that cannot lead to a valid answer.

The number of valid combinations is the Catalan number:

Catalan number

Complexity:
Time complexity is O(n * Cn) to produce all strings.
Space complexity - O(n) for recursion and the current path, or O(n * Cn) including the output.


What should remember: Formulate constraints that guarantee validity during construction, instead of generating everything and checking afterward. This generalizes to combinatorial search, permutations, subsets, constraint satisfaction, and DFS.



32. Longest Valid Parentheses

Pattern: Stack + index tracking

Goal: Find the length of the longest contiguous valid parentheses substring.

Example: )()()) gives 4, because ()() is the longest valid substring.


Why store indices rather than characters?

Problem 20 only asks whether a string is valid. Here, we must calculate a length, so positions matter.

A stack-based solution begins with [-1], a sentinel boundary before the string:

  1. On (, push its index.
  2. On ), pop the top index.
  3. If the stack is nonempty, update the answer with i - stack.top.
  4. If the stack becomes empty, push the current index as the new boundary.

Why initialize the stack with -1?

For ()(), the last character is at index 3. After all matching opening parentheses have been popped, -1 remains as the left boundary:

length = 3 - (-1) = 4

Without this sentinel, a separate case would be needed for substrings beginning at index 0.


Complexity:
Time complexity: O(n)
Space complexity: O(n) for the stack.


Alternative approaches include Dynamic Programming with O(n) space and a two-pass counter method with O(1) auxiliary space.


What should remember: A stack can store positions and boundaries, not just values. This is the transition from simple matching to interval and length analysis.



678. Valid Parenthesis String

Pattern: Greedy + range tracking

Goal: Check whether a string is valid when * can represent (, ), or an empty string.

Example: (*)) is valid because * can represent (.


Why isn't a simple stack the natural solution?

In Problem 20, every character has a fixed meaning. Here, each * creates three possibilities. Backtracking through all choices can take exponential time.

Instead of choosing one meaning for each *, we maintain a range of possible unmatched opening-parenthesis counts:

  • low: minimum feasible number of unmatched (.
  • high: maximum feasible number of unmatched (.

Updates:

Character: (, where low change is +1 and high change is +1
Character: ), where low change is -1 and high change is -1
Character: *, where low change is -1 and high change is +1


After every character, clamp low = max(0, low).

If high < 0, every interpretation has too many closing parentheses, so the string is invalid. At the end, the string is valid if low == 0.


Step-by-step example: (*))

Character processed: (, where low is 1 and high is 1 - one unmatched opening parenthesis
Character processed: *, where low is 0 and high is 2 - the wildcard can close, do nothing, or open
Character processed: ), where low is 0 and high is 1 - Oone possible opening parenthesis is closed
Character processed: ), where low is 0 and high is 0 - a fully balanced interpretation exists


Why is this greedy pattern?

We do not store every interpretation. We keep only the lower and upper bounds needed to decide whether a valid interpretation remains possible.


Complexity:
Time complexity: O(n)
Space complexity: O(1)


What should remember: Sometimes we do not need the exact state. Tracking a compact set of possible states-or just its bounds-is enough. This is useful in greedy algorithms, interval reasoning, and state-space compression.



1190. Reverse substrings between each pair of parentheses

Pattern: Stack / pair mapping + direction reversal

Goal: Reverse the characters inside each matched pair of parentheses, from the innermost pair outward, and remove all parentheses.

Example:

Input:  (u(love)i)
Output: iloveu

Approach 1: Stack

When we encounter ), reverse the accumulated characters back to the corresponding (.

A stack naturally supports this because the innermost pair closes first. However, with deeply nested parentheses, the same characters may be moved or reversed repeatedly.


Worst-case complexity:
Time complexity: O(n2)
Space complexity: O(n)


Approach 2: Pair mapping

A more efficient approach avoids physically reversing substrings:

  1. Use a stack to find each opening parenthesis's matching closing parenthesis.
  2. Store matching indices in a lookup array.
  3. Traverse the string, initially moving from left to right.
  4. On reaching either parenthesis, jump to its matching partner and reverse the traversal direction.
  5. Append only non-parenthesis characters to the result.

For (u(love)i), the matched index pairs are (0, 9) and (2, 7). These pairs act as jump points that change the reading direction.


Complexity:
Time complexity: O(n)
Space complexity: O(n)


What should remember: You do not always have to perform an operation literally. Changing the traversal order can produce the same result without repeatedly modifying the data. This principle applies to string processing, permutations, and indirect indexing.



The fundamental difference between the problems

Before choosing a pattern, ask:

What is the minimum information required to make the next correct decision?


20. Valid Parentheses.
Need to remember - type of the most recent unmatched opening bracket because to check correct matching and nesting
22. Generate Parentheses.
Need to remember - number of opening and closing parentheses used because to construct only valid prefixes
32. Longest Valid Parentheses.
Need to remember - indices of unmatched parentheses and boundaries because to calculate substring lengths
678. Valid Parenthesis String.
Need to remember - minimum and maximum feasible balance because to represent multiple interpretations
1190 Reverse Substrings Between Each Pair of Parentheses.
Need to remember - positions of matching parentheses because to navigate nested reversals efficiently

This information requirement—not the presence of parentheses—determines the best algorithm.


Five important algorithmic lessons

1. Use a stack because of LIFO dependencies, not merely because parentheses appear

A stack is appropriate when the most recently opened item must be completed first. Problems 20, 32, and 1190 all use this property, but for different purposes.


Problem 22 teaches you to define constraints that eliminate impossible branches early. Effective pruning is often more important than the recursive structure itself.


3. A greedy representation can replace exponential exploration

Problem 678 has many interpretations of *, but two numbers-low and high-can represent everything needed for validation. This is a form of state compression.


4. Indices can matter more than values

Problem 32 shows that knowing which brackets match is not enough to find the longest valid substring. Their positions are essential.


5. Optimization often comes from changing the model

In Problem 1190, the straightforward approach repeatedly reverses substrings. The more efficient approach changes how the string is traversed. This is a powerful general technique: avoid expensive operations by finding an equivalent representation.


Questions to ask before choosing a pattern

Must I process the most recently unfinished item first? If yes - Stack for completion follows reverse order
Must I generate all valid combinations? If yes - Backtracking for building candidates while pruning invalid prefixes
Must I find the longest or best contiguous segment? If yes - Indices / DP for tracking boundaries or optimal subproblem results
Can many possible states be represented as a range? If yes Greedy + range tracking for compressing the state space
Can I avoid repeated mutations by changing traversal order? If yes - mapping + traversal for replacing physical transformations with navigation


Conclusion

The main value of these five problems is not memorizing five solutions. Each develops a distinct skill:

20: Recognize the order of dependencies.
22: Construct solutions without generating invalid candidates.
32: Move from validity checking to optimal interval analysis.
678: Replace exploration of many states with a compact representation.
1190: Avoid unnecessary operations by changing the traversal strategy.


! Choose an algorithmic pattern based on the information that must be stored and processed - not on the superficial appearance of the problem.