- In this article we will solve Leetocode 1021 problem, this problem helps us understand stack data structure and how to use them.
- We have been given valid parentheses and we need to remove the outermost parentheses of every primitive string.
- A valid parentheses string
sis primitive if it is nonempty, and there does not exist a way to split it into
s = A + B, with
Bnonempty valid parentheses strings.
- Given a valid parentheses string
s, consider its primitive decomposition:
s = P1 + P2 + ... + Pk, where
Piare primitive valid parentheses strings.
- In the below example, we are decomposing strings into “(()())” + “(())”
- Now from the first primitive string, we remove the outermost parentheses -> “()()”. For the next primitive string “()”.
- Intuition is that we will iterate through each character and when we encounter opening parentheses we push to stack. while pushing to the stack we will check if there are at least 1 open parentheses and if that is the case that means we already covered outer parentheses so current open parentheses are part of the output.
- If the encounter string is closing parentheses then we again check if the stack size is greater than 1. please notice here we need at least more than 1 opening parentheses in the stack so that we can consider adding closing parentheses to the result.
- Here is the entire code.
def remove_outer_parentheses(s) stack =  res = "" s.chars.each do |c| if c == '(' if stack.size >= 1 res<<c end stack.push(c) elsif c== ')' if stack.size > 1 res<<c end stack.pop() end end res end
- Now since the character that we are storing in the stack is the same, we can instead maintain opened parentheses var and use it for our logic.
def remove_outer_parentheses(s) open = 0 res = "" s.chars.each do |c| if c == '(' if open >= 1 res<<c end open+=1 elsif c == ')' if open > 1 res<<c end open-=1 end end res end
- Our code is accepted by Leetcode.
Time Complexity: O(N)
with stack -> O(m) -> m = max depth of parentheses
without stack -> O(1)
- In this article, we solved Leetcode 1021, which help us to understand how to use stack data structure.
- We also realized if the data that is stored in the stack is the same we can instead maintain a variable instead of creating the stack.
- If you want to upskill your coding interview game, you can definitely check out this bestseller course ( this is in Java )