Reverse Substrings Between Each Pair of Parentheses

Introduction

Hi friends! Welcome to 100 Days of Leetcode Challenge. In this article, we going to see about Reverse Substrings Between Each Pair of Parentheses.

Language

I took C# programming language to solve this problem. Since language is independent of the problem. You can use whatever language you wish to solve. Only problem solving approach(logic) is important.

Day 32

You are given a string s that consists of lower case English letters and brackets. 

Reverse the strings in each pair of matching parentheses, starting from the innermost one.

Your result should not contain any brackets.

Example 1:

Input: s = "(abcd)"
Output: "dcba"

Example 2:

Input: s = "(u(love)i)"
Output: "iloveu"
Explanation: The substring "love" is reversed first, then the whole string is reversed.

Example 3:

Input: s = "(ed(et(oc))el)"
Output: "leetcode"
Explanation: First, we reverse the substring "oc", then "etco", and finally, the whole string.

Example 4:

Input: s = "a(bcdefghijkl(mno)p)q"
Output: "apmnolkjihgfedcbq"

Approach

Normal Brute Force Approach

  1. Store the open bracket indexes at stack.
  2. Whenever you get close bracket, pop from the stack, reverse the char array by using open bracket index and close bracket index.
  3. Finally replace, “(” and “)” with empty character and return the string.
public class Solution {
    public string ReverseParentheses(string s) {
        //Add the open bracket indexes at stack
        Stack<int> stack = new Stack<int>();
        char[] c = s.ToCharArray();
        for(int i=0;i<c.Length;i++)
        {
            char ch = c[i];
            
            if(ch == '(')
                stack.Push(i);
            else if(ch == ')')
            {
                int openIndex = stack.Pop();
                int closeIndex = i;
                Array.Reverse(c,openIndex+1,closeIndex-openIndex-1);
            }
        }
        string result = new string(c);
        result = result.Replace("(","").Replace(")","");
        return result;
    }
}

Time Complexity : O(n * m)

Space Complexity : O(n)

How can we improve the time complexity to O(n), is this possible?

Yes it is possible. Thanks to lee215 for this better approach. This solution credits goes to lee215 in Leetcode.

Explanation

In the first pass,
use a stack to find all paired parentheses,
I assume you can do this.

Now just imgine that all parentheses are wormholes.
As you can see in the diagram,
the paired parentheses are connected to each other.

image

First it follows the left green arrrow,
go into the left wormhole and get out from the right wormhole.
Then it iterates the whole content between parentheses.
Finally it follows the right arrow,
go into the left wormhole,
get out from the right wormhole and finish the whole trip.

So in the second pass of our solution,
it traverses through the paired parentheses
and generate the result string res.

i is the index of current position.
d is the direction of traversing.

Complexity

Time O(N) for two passes
Space O(N)

Best Solution

public class Solution {
    public string ReverseParentheses(string s) {
        int n = s.Length;
        //Add the open bracket indexes at stack
        Stack<int> opened = new Stack<int>();
        int[] pair = new int[n];
        for(int i=0;i<n;i++)
        {
            if(s[i] == '(')
                opened.Push(i);
            else if(s[i] == ')')
            {
                int j = opened.Pop();
                pair[j] = i;
                pair[i] = j;
            }
        }
        StringBuilder sb = new StringBuilder();
        //Direction of traversing
        int d = 1;
        for(int i=0;i<n;i+=d)
        {
            if(s[i] == '(' || s[i] == ')')
            {
                i = pair[i];
                d = -d;
            }
            else
                sb.Append(s[i]);
        }
        return sb.ToString();
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s