1190. Reverse Substrings Between Each Pair of Parentheses

1190. Reverse Substrings Between Each Pair of Parentheses

Medium

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 resu…


This content originally appeared on DEV Community and was authored by MD ARIFUL HAQUE

1190. Reverse Substrings Between Each Pair of Parentheses

Medium

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.

Solution:

Here's the step-by-step plan:

  1. Use a stack to keep track of the characters and nested parentheses.
  2. Traverse each character in the string.
  3. If you encounter an opening parenthesis '(', push it onto the stack.
  4. If you encounter a closing parenthesis ')', pop from the stack until you reach an opening parenthesis '('. Reverse the substring collected and push it back onto the stack.
  5. Finally, concatenate the stack contents to get the result.

Here's the implementation in PHP: 1190. Reverse Substrings Between Each Pair of Parentheses

<?php
// Example 1
echo reverseParentheses("(abcd)") . "\n"; // Output: "dcba"

// Example 2
echo reverseParentheses("(u(love)i)") . "\n"; // Output: "iloveu"

// Example 3
echo reverseParentheses("(ed(et(oc))el)") . "\n"; // Output: "leetcode"
?>

Explanation

  • The function reverseParentheses takes a string s as input.
  • A stack is used to keep track of characters and nested parentheses.
  • As we traverse the string:
    • If we encounter a closing parenthesis ), we start popping from the stack until we find an opening parenthesis (.
    • We collect the characters popped (which are inside the parentheses), reverse them, and push them back onto the stack.
    • If the character is not a closing parenthesis, it is directly pushed onto the stack.
  • Finally, we concatenate the elements of the stack to form the result string, ensuring that the brackets are not included.

This method efficiently handles nested parentheses and ensures the correct order of characters after reversing the substrings within each pair of parentheses.

Contact Links


This content originally appeared on DEV Community and was authored by MD ARIFUL HAQUE


Print Share Comment Cite Upload Translate Updates
APA

MD ARIFUL HAQUE | Sciencx (2024-07-11T16:09:43+00:00) 1190. Reverse Substrings Between Each Pair of Parentheses. Retrieved from https://www.scien.cx/2024/07/11/1190-reverse-substrings-between-each-pair-of-parentheses/

MLA
" » 1190. Reverse Substrings Between Each Pair of Parentheses." MD ARIFUL HAQUE | Sciencx - Thursday July 11, 2024, https://www.scien.cx/2024/07/11/1190-reverse-substrings-between-each-pair-of-parentheses/
HARVARD
MD ARIFUL HAQUE | Sciencx Thursday July 11, 2024 » 1190. Reverse Substrings Between Each Pair of Parentheses., viewed ,<https://www.scien.cx/2024/07/11/1190-reverse-substrings-between-each-pair-of-parentheses/>
VANCOUVER
MD ARIFUL HAQUE | Sciencx - » 1190. Reverse Substrings Between Each Pair of Parentheses. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2024/07/11/1190-reverse-substrings-between-each-pair-of-parentheses/
CHICAGO
" » 1190. Reverse Substrings Between Each Pair of Parentheses." MD ARIFUL HAQUE | Sciencx - Accessed . https://www.scien.cx/2024/07/11/1190-reverse-substrings-between-each-pair-of-parentheses/
IEEE
" » 1190. Reverse Substrings Between Each Pair of Parentheses." MD ARIFUL HAQUE | Sciencx [Online]. Available: https://www.scien.cx/2024/07/11/1190-reverse-substrings-between-each-pair-of-parentheses/. [Accessed: ]
rf:citation
» 1190. Reverse Substrings Between Each Pair of Parentheses | MD ARIFUL HAQUE | Sciencx | https://www.scien.cx/2024/07/11/1190-reverse-substrings-between-each-pair-of-parentheses/ |

Please log in to upload a file.



There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.

Related Posts