1190 LeetCode problem solution

LeetCode problem link: 1190. Reverse Substrings Between Each Pair of Parentheses


LeetCode 1190. Reverse Substrings Between Each Pair of Parentheses description

Medium level problem.


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.


Constraints:

  • 1 <= s.length <= 2000
  • s only contains lower case English characters and parentheses.
  • It is guaranteed that all parentheses are balanced.

LeetCode 1190 problem solution

In this problem I use a stack to find and store the matching position for every pair of parentheses.

First, I scan the string from left to right and push the index of each ( onto the stack. When ) is found, match it with the latest ( from the stack and store both positions in a pair array.

Then traverse the string again using a direction value. Start from left to right with direction = 1. When a parenthesis is reached, jump directly to its matching parenthesis and reverse the traversal direction.

Letters are added to the result in the order they are visited but parentheses are skipped. This simulates all required reversals without actually reversing any substring.


Patterns | Techniques | Data Structures

Stack - data structure
Parentheses Pair Mapping - technique
Direction Reversal - technique


Complexity

Time complexity: O(n) - because one pass builds the matching pairs and one pass constructs the result. Space complexity: O(n) - because the stack and pair array store parenthesis positions.


LeetCode 1190 problem example

For:

s = "(u(love)i)"

First, match the parentheses:

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

pairs:
from 0 to 9
and from 2 to 7

Start at index 0 with:

direction = 1

At (, jump from index 0 to index 9 and reverse the direction:

direction = -1

Now move backward:

9 -> 8
     i

Add i.

At index 7, ) is found, jump to its matching ( at index 2 and reverse the direction again:

direction = 1

Continue forward through:

l -> o -> v -> e

At index 7, jump back to index 2 and change direction to -1.

if(s[i] == '(' || s[i] == ')') {
  i = pair[i];               // 7 to 2
  direction = -direction;    // 1 is -1
}

Continue backward and visit:

u

Let's see full transition:

index 7 ')' is pair[7]
index 2 '(' are:
  direction = -1
  i += direction  // i = 2 + (-1) = 1
                  // where i += direction is the third part of the for loop
index 1 'u'

The letters are visited in this order:

i -> l -> o -> v -> e -> u

Final result:

iloveu

LeetCode 1190 C++ solution

class Solution {
public:
  string reverseParentheses(string s) {
    int n = s.size();

    vector<int> pair(n);
    stack<int> st;

    // Match every '(' with its ')'
    for(int i = 0; i < n; i++)
    {
      if(s[i] == '(') st.push(i);
      else if(s[i] == ')')
      {
        int j = st.top();
        st.pop();

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

    string result;

    // Traverse the string.
    // When we meet a parenthesis, jump to its pair and reverse the traversal direction.
    for(int i = 0, direction = 1; i < n; i += direction)
    {
      if(s[i] == '(' || s[i] == ')')
      {
        i = pair[i];
        direction = -direction;
      }
      else result += s[i];
    }

    return result;
  }
};

LeetCode 1190 Java solution

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

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

    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();

    for(int i = 0, direction = 1; i < n; i += direction) {
      char c = s.charAt(i);

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

    return result.toString();
  }
}

LeetCode 1190 JavaScript solution

var reverseParentheses = function(s) {
  const n = s.length;

  const pair = new Array(n);
  const stack = [];

  for(let i = 0; i < n; i++) {
    if(s[i] === '(') {
      stack.push(i);
    } else if (s[i] === ')') {
      const j = stack.pop();

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

  let result = '';

  for(let i = 0, direction = 1; i < n; i += direction) {
    if(s[i] === '(' || s[i] === ')') {
      i = pair[i];
      direction = -direction;
    } else {
      result += s[i];
    }
  }

  return result;
};

LeetCode 1190 TypeScript solution

function reverseParentheses(s: string): string {
  const n = s.length;

  const pair: number[] = new Array(n);
  const stack: number[] = [];

  for(let i = 0; i < n; i++) {
    if(s[i] === '(') {
      stack.push(i);
    } else if(s[i] === ')') {
      const j = stack.pop()!;

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

  let result = '';

  for(let i = 0, direction = 1; i < n; i += direction) {
    if(s[i] === '(' || s[i] === ')') {
      i = pair[i];
      direction = -direction;
    } else {
      result += s[i];
    }
  }

  return result;
}

LeetCode 1190 Python solution

class Solution:
  def reverseParentheses(self, s: str) -> str:
    n = len(s)

    pair = [0] * n
    stack = []

    for i, c in enumerate(s):
      if c == '(':
        stack.append(i)
      elif c == ')':
        j = stack.pop()

        pair[i] = j
        pair[j] = i

    result = []

    i = 0
    direction = 1

    while i < n:
      if s[i] == '(' or s[i] == ')':
          i = pair[i]
          direction = -direction
      else:
        result.append(s[i])

      i += direction

    return ''.join(result)