Reverse Substrings Between Each Pair of Parentheses | 2 Approaches | Leetcode 1190 |codestorywithMIK
394Whatsapp Community Link : https://www.whatsapp.com/channel/0029...
This is the 18th Video of our Playlist "Stack : Popular Interview Problems" by codestorywithMIK
In this video we will try to solve a good Stack based problem : Reverse Substrings Between Each Pair of Parentheses | 2 Approaches | Leetcode 1190 | codestorywithMIK
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Reverse Substrings Between Each Pair of Parentheses | 2 Approaches | Leetcode 1190 | codestorywithMIK
Company Tags : META, AMAZON
My solutions on Github(C++ & JAVA) : https://github.com/MAZHARMIK/Intervie...
Leetcode Link : https://leetcode.com/problems/reverse...
My DP Concepts Playlist : • Roadmap for DP | How to Start DP ? | ...
My Graph Concepts Playlist : • Graph Concepts & Qns - 1 : Graph will...
My Recursion Concepts Playlist : • Introduction | Recursion Concepts And...
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Intervie...
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Summary :
Approach 1: Brute Force
Time Complexity: O(n2)
Space Complexity: O(n)
This approach uses a stack (or a vector acting as a stack) to store the indices of open parentheses (. It iterates through the string and performs the following steps:
When encountering (, push the current length of the result string onto the stack.
When encountering ), pop the last index from the stack, reverse the substring from this index to the current end of the result string.
Append all other characters directly to the result string.
This method involves reversing substrings multiple times, leading to O(n2) time complexity in the worst case.
Approach 2: Linear Approach
Time Complexity: O(n)
Space Complexity: O(n)
This approach involves two passes through the string to achieve an efficient linear time solution:
First Pass: Use a stack to pair up the indices of matching parentheses. Store these pairs in an array door.
When encountering (, push the index onto the stack.
When encountering ), pop the index of the last ( from the stack and store the pair in door.
Second Pass: Build the result string while considering direction changes.
Start with the left-to-right direction.
When encountering a parenthesis, switch direction and jump to the paired index using door.
Append all other characters directly to the result string.
This method ensures efficient processing by utilizing index mapping and direction control, leading to O(n) time complexity.
✨ Timelines✨
00:00 - Introduction
1:28 - Approach-1 (Brute Force)
19:05 - Approach-2 (Warmhole Teleportation)
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #newyear2024