LeetCode 1190: Stack vs. DP vs. Optimal Solution

Link to LeetCode 1190. Reverse Substrings Between Each Pair of Parentheses problem.

In this article, I'll explore three different approaches to solving LeetCode 1190: Reverse Substrings Between Each Pair of Parentheses:
1. Stack - store parts of the string and reverse them whenever we encounter a closing parenthesis ).
2. Dynamic Programming (DP) - reuse the results of previously processed nested substrings to build the results for outer substrings.
3. Stack + Paired Indices - an optimized approach that avoids physically reversing substrings.

I'll explain each algorithm step by step and compare their time complexity, space complexity, and implementation difficulty.

Short problem description

Given a string s containing lowercase English letters and parentheses, reverse the substrings inside each pair of matching parentheses, starting from the innermost pair. The final result must not contain any parentheses.

Example:

Input: 
s = "(u(love)i)""

Steps:
1. (love) -> evol
2. (uevoli) -> iloveu

Output:
"iloveu"

The key observation is that nested parentheses must be processed before their enclosing parentheses.

Solution using a Stack

Algorithm idea

A stack follows the LIFO (Last In, First Out) principle - the last element added is the first one removed.
This makes it suitable for nested parentheses because the most recently opened parenthesis must be closed first.
We use two structures:

Deque<StringBuilder> stack - stores the parts of the string that appear before each opening parenthesis.
StringBuilder current - collects characters at the current nesting level.

When we encounter (, we push current onto the stack and create a new StringBuilder. When we encounter ), we reverse current, pop the previous string from the stack, and append the reversed substring.

Complexity analysis

Time complexity: O(n²) in the worst case.

We iterate through all characters - O(n).
Each reverse() takes O(k) time, where k is the length of the current substring.
With deeply nested parentheses, the same characters may be reversed multiple times, resulting in O(n²) total time complexity.

Important: We don't automatically multiply n * k just because reverse() is inside a loop. The quadratic complexity comes from the cumulative cost of repeated reversals.

For example, s = "((((abcdef))))". There are 4 nested pairs of parentheses.
Each time we encounter ), we execute:

current.reverse();
current = stack.pop().append(current);

Now consider a string containing:

k nested pairs of parentheses.
m characters inside the innermost pair.

Every character is reversed k times. Therefore, the total work is T(n) = O(k * m)

Since both k and m can be proportional to the input length n, we get T(n) = O(n²)

Why not O(n)?
The outer for loop visits each character only once, current.reverse() processes multiple characters internally. Therefore, one iteration of the loop is not necessarily O(1).

Key takeaway: a single loop does not guarantee O(n) time complexity when operations inside that loop depend on the input size.

Space complexity: O(n).
The stack and all StringBuilder instances collectively store O(n) characters and stack entries.

Java solution

class Solution {
  public String reverseParentheses(String s) {
    Deque<StringBuilder> stack = new ArrayDeque<>();
    StringBuilder current = new StringBuilder();

    for (char c : s.toCharArray()) {
      if (c == '(') {
        stack.push(current);
        current = new StringBuilder();
      } else if (c == ')') {
        current.reverse();
        current = stack.pop().append(current);
      } else {
        current.append(c);
      }
    }

    return current.toString();
  }
}

Solution using Dynamic Programming (DP)

An important detail: LeetCode 1190 is not a classic Dynamic Programming problem. It is usually solved using a stack or matching parenthesis indices. However, we can implement a valid DP solution by storing the processed results of nested substrings.

Algorithm idea

Instead of processing the entire string using a single stack of partial strings, we compute the result for each substring enclosed by a matching pair of parentheses.

Define: dp[i] - the fully processed and reversed substring enclosed by the opening parenthesis at index i.

For example:

s = "(u(love)i)"

dp[2] = "evol"
dp[0] = "iloveu"

We first calculate the result for the innermost pair and then reuse it when processing the outer pair.

Step-by-Step explanation

Step 1. Find matching parentheses.

For the string:

Index:  0 1 2 3 4 5 6 7 8 9
Char:   ( u ( l o v e ) i )

We obtain:

pair[0] = 9
pair[2] = 7

Step 2. Calculate DP states from right to left.

We start with i = 2 because it represents the inner opening parenthesis.

dp[2] = reverse("love")

We obtain "evol". Next, we process i = 0.
We construct the contents of the outer parentheses using the previously calculated result:

"u" + dp[2] + "i" = "u" + "evol" + "i" = "uevoli"

Then reverse the entire substring:

dp[0] = reverse("uevoli") = "iloveu"

Step 3. Build the final result.

We iterate through the original string. Whenever we encounter (, we append the corresponding dp[i] and skip directly to the matching closing parenthesis. In this example, the final result is dp[0], which equals "iloveu".

Why is this Dynamic Programming?

Because we reuse the results of smaller, previously solved subproblems to construct the results of larger subproblems. Unlike traditional DP problems involving numerical values, the states in this solution store strings.

Complexity analysis

Time complexity: O(n²) in the worst case.

Finding matching parentheses takes O(n).
Computing all dp[i] states takes up to O(n²) because characters may be copied multiple times across nested substrings.
Building the final result takes O(n).

Space complexity: O(n²) in the worst case.
The dp array stores strings, and the same character may appear in multiple nested DP results.

For example, with ((((abc)))), each nesting level stores its own copy of abc. In the worst case, the total length of all stored strings grows quadratically.

Java solution

class Solution {
  public String reverseParentheses(String s) {
    int n = s.length();

    int[] pair = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();

    // Find matching parentheses
    for (int i = 0; i < n; i++) {
      if (s.charAt(i) == '(') {
        stack.push(i);
      } else if (s.charAt(i) == ')') {
        int open = stack.pop();
        pair[open] = i;
      }
    }

    // dp[i] stores the processed substring starting at opening parenthesis i
    String[] dp = new String[n];

    for (int i = n - 1; i >= 0; i--) {
      if (s.charAt(i) != '(') {
        continue;
      }

      StringBuilder current = new StringBuilder();

      for (int j = i + 1; j < pair[i]; j++) {
        if (s.charAt(j) == '(') {
          current.append(dp[j]);
          j = pair[j];
        } else {
          current.append(s.charAt(j));
        }
      }

      dp[i] = current.reverse().toString();
    }

    StringBuilder result = new StringBuilder();

    for (int i = 0; i < n; i++) {
      if (s.charAt(i) == '(') {
        result.append(dp[i]);
        i = pair[i];
      } else {
        result.append(s.charAt(i));
      }
    }

    return result.toString();
  }
}

Can we do better than O(n²)?

Yes. There is a more efficient algorithm using Stack + Paired Indices, which runs in O(n) time.
The main idea is to avoid physically reversing substrings.
Instead, we:

Find the matching pair for each parenthesis using a stack.
Start traversing the string from left to right.
Whenever we encounter a parenthesis, jump to its matching pair and reverse the traversal direction.
Append only letters to the result.

Why does this work?

Each time we encounter a parenthesis, we jump to its matching parenthesis and reverse the traversal direction.
This effectively simulates reversing the substring without modifying the original string.
Every character is visited exactly once during the final traversal.

In this case:

Time complexity: O(n)

Finding matching parentheses takes O(n).
Traversing the string and constructing the result takes O(n).

Space complexity: O(n)

The pair array requires O(n) space.
The stack requires up to O(n) space.
The output string requires up to O(n) space.

Java solution

class Solution {
  public String reverseParentheses(String s) {
    int n = s.length();

    int[] pair = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < n; i++) {
      if (s.charAt(i) == '(') {
        stack.push(i);
      } else if (s.charAt(i) == ')') {
        int j = stack.pop();

        pair[i] = j;
        pair[j] = i;
      }
    }

    StringBuilder result = new StringBuilder();

    int i = 0;
    int direction = 1;

    while (i < n && i >= 0) {
      char c = s.charAt(i);

      if (c == '(' || c == ')') {
        i = pair[i];
        direction = -direction;
      } else {
        result.append(c);
      }

      i += direction;
    }

    return result.toString();
  }
}

Conclusion

Stack + StringBuilder - the easiest solution to implement and explain. It naturally handles nested parentheses but may repeatedly reverse the same characters.
Stack + Paired Indices - the optimal solution - O(n) time and O(n) space complexity. It avoids unnecessary string reversals by jumping between matching parentheses and changing the traversal direction.
Dynamic Programming is also possible, but it does not provide a performance advantage for this particular problem.

LeetCode 1190: Stack vs. DP vs. Optimal Solution

Short problem description

Solution using a Stack

Algorithm idea

Complexity analysis

Solution using Dynamic Programming (DP)

Algorithm idea

Step-by-Step explanation

Step 1. Find matching parentheses.

Step 2. Calculate DP states from right to left.

Step 3. Build the final result.

Why is this Dynamic Programming?

Complexity analysis

Can we do better than O(n2)?

Why does this work?

Conclusion

Can we do better than O(n²)?