DDSA Solutions

1190. Reverse Substrings Between Each Pair of Parentheses

MediumView on LeetCode
StringStack

Problem Overview

Each pair of parentheses reverses the text inside it, and a nested pair reverses that piece again.

Intuition

Each pair of parentheses reverses the text inside it, and a nested pair reverses that piece again. Matching every bracket first lets one walk produce the final order. When the walk hits a parenthesis it jumps to the partner and turns around, so the enclosed letters are read backwards without copying that span into a new string.

Algorithm

  1. 1Scan the string with a stack of opening indexes. Each closing parenthesis pops its match, and the two indexes point at each other.
  2. 2Start at the first character and move forward.
  3. 3A letter is appended, then the walk takes one step in the current direction.
  4. 4A parenthesis jumps to the stored partner and flips the direction. The following step lands just inside the pair, which is where the reversed reading continues.
  5. 5The walk ends when the index leaves the string. The builder holds the answer.

Example Walkthrough

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

  1. 1.The outer parentheses sit at the two ends, and the inner pair wraps love.
  2. 2.The walk enters through the outer opening, jumps to the end, and reads i while moving left.
  3. 3.The inner closing parenthesis jumps to its opening and flips direction, so love is read from left to right.
  4. 4.After love the walk is moving left again and appends u.

Output: "iloveu"

Common Pitfalls

  • •Reversing each span as soon as it closes copies the same letters many times and is quadratic.
  • •The jump lands on the partner, and the direction step then moves past it. Do not also skip that partner by hand.
  • •Parentheses are never written. Only letters go into the result.
  • •Each boundary flips the direction once, so an inner span is reversed again by every outer pair that contains it.
1190.cs
C#
// Approach: Pair each parenthesis with its match. Walk the string with a
// direction. Hitting '(' or ')' jumps to the partner and flips direction,
// which writes the enclosed letters in reverse without copying the span.
// Complexity: O(n) time, O(n) extra space.
public class Solution
{
    public string ReverseParentheses(string s)
    {
        int n = s.Length;
        int[] pair = new int[n];
        var stack = new Stack<int>();

        for (int i = 0; i < n; i++)
        {
            if (s[i] == '(')
                stack.Push(i);
            else if (s[i] == ')')
            {
                int open = stack.Pop();
                pair[i] = open;
                pair[open] = i;
            }
        }

        var sb = new StringBuilder();
        for (int i = 0, dir = 1; i < n; i += dir)
        {
            if (s[i] == '(' || s[i] == ')')
            {
                i = pair[i];
                dir = -dir;
            }
            else
            {
                sb.Append(s[i]);
            }
        }

        return sb.ToString();
    }
}
Was this solution helpful?

Related Problems