1021. Remove Outermost Parentheses

Remove Outermost Parentheses 

Problem Description

A valid parentheses string is either empty "", "(" + A + ")", or A + B, where A and B are valid parentheses strings, and + represents string concatenation.For example, "", "()", "(())()", and "(()(()))" are all valid parentheses strings.

A valid parentheses string s is primitive if it is nonempty, and there does not exist a 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 is primitive valid parentheses strings.

Return s after removing the outermost parentheses of every primitive string in the primitive decomposition of s.

 

Example 1:

Input: s = "(()())(())"
Output: "()()()"
Explanation: 
The input string is "(()())(())", with primitive decomposition "(()())" + "(())".
After removing outer parentheses of each part, this is "()()" + "()" = "()()()".

Example 2:

Input: s = "(()())(())(()(()))"
Output: "()()()()(())"
Explanation: 
The input string is "(()())(())(()(()))", with primitive decomposition "(()())" + "(())" + "(()(()))".
After removing outer parentheses of each part, this is "()()" + "()" + "()(())" = "()()()()(())".

Example 3:

Input: s = "()()"
Output: ""
Explanation: 
The input string is "()()", with primitive decomposition "()" + "()".
After removing outer parentheses of each part, this is "" + "" = "".

 

Constraints:

• 1 <= s.length <= 105
• s[i] is either '(' or ')'.
• s is a valid parentheses string.

Approach (Using Stack)

/**
 * @param {string} s
 * @return {string}
 */
var removeOuterParentheses = function(s) {
    let result = [];
    let stack = new Stack()
    for(let i=0;i<s.length;i++){
        let char  = s[i];
         if (stack.isEmpty()){
             if (char=='('){
                 stack.push('(');
             }
         }else {
            if(char == ')' && stack.size() == 1){
                stack.pop();
            }else{
                result.push(char);
                if(char == '('){
                   stack.push(char);
                }else{
                    stack.pop()
                }
            }
         }
    }
    return result.join("");
};

class Stack {
    constructor() {
        this.stack = []
    }
    push(a) {
        this.stack.push(a)
    }
    pop() {
        return this.stack.pop()
    }
    peek() {
        return this.stack[this.stack.length - 1]
    }
    size() {
        return this.stack.length
    }
    toString(){
      return this.stack.join("");  
    }
    isEmpty() {
        return this.stack.length == 0
    }
}

Runtime: 63 ms, faster than 97.88% of JavaScript online submissions for Remove Outermost Parentheses.
Memory Usage: 43.7 MB, less than 68.18% of JavaScript online submissions for Remove Outermost Parentheses.

Complexity analysis

Time Complexity

We are traversing through the complete array which needs O(N).

Space Complexity

Since we are using any extra space as a stack, hence space complexity is O(N).

Conclusion

That’s all folks! In this post, we solved LeetCode problem #1021. Remove Outermost Parentheses 

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!