Blog

Introduction

• In this article we will solve Leetocode 1021 problem, this problem helps us understand stack data structure and how to use them.

Problem Statement

• We have been given valid parentheses and we need to remove the outermost parentheses of every primitive string.
• A valid parentheses string s is primitive if it is nonempty, and there does not exist way to split it into s = A + B, with A and B nonempty valid parentheses strings.
• Given a valid parentheses string s, consider its primitive decomposition: s = P1 + P2 + ... + Pk, where Pi are primitive valid parentheses strings.

Example

• 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 “()”.

Solution

Intuition

•  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 result.

Code

• Here is the entire code.

    private String sol1(String s){
        Stack<Character> stack = new Stack<>();
        StringBuilder res = new StringBuilder();
        
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='('){
                if(stack.size()>=1){
                    res.append(""+s.charAt(i));
                }
                stack.push(s.charAt(i));
            }else{
                
                if(stack.size()>1){
                    res.append(""+s.charAt(i));
                }
                stack.pop();
            }
        }
        
        return res.toString();
    }

• 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.

private String sol2(String s){
        int opened = 0;
        StringBuilder res = new StringBuilder();
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='('){
                opened++;
                if(opened>1){
                    res.append(""+s.charAt(i));
                }
            }else{
                opened--;
                if(opened>0){
                    res.append(""+s.charAt(i));
                }
            }
        }
        
        return res.toString();
        
    }

Result

• Our code is accepted by Leetcode.

Complexity

Time Complexity: O(N)
Space Complexity: 
with stack -> O(m) -> m = max depth of parentheses
without stack -> O(1)

Conclusion

• 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.

Bonus Tip

• If you want to upskill your coding interview game, you can definitely check out this bestseller course ( this is in Java )