Remove Outermost Parentheses LeetCode Solution - The Coding Shala

Home >> LeetCode >> Remove Outermost Parentheses

 In this post, we will learn how to solve LeetCode's Remove Outermost Parentheses problem and will implement its solution in Java.

Remove Outermost Parentheses Problem

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.

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

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

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

Practice this problem on LeetCode.

LeetCode - Remove Outermost Parentheses Java Solution

Approach 1

Iterative Solution.

Java Program: 

class Solution {
    public String removeOuterParentheses(String S) {
        int cnt = 0;
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<S.length(); i++) {
            if(cnt == 0) {
                cnt++;
            } else if(cnt == 1 && S.charAt(i) == ')') {
                cnt--;
            } else {
                sb.append(S.charAt(i));
                if(S.charAt(i) == '(') cnt++;
                else cnt--;
            }
        }
        return sb.toString();
    }
}

Approach 2

Using Stack.

Java Program: 

class Solution {
    public String removeOuterParentheses(String S) {
        Stack<Character> stack = new Stack<>();
        StringBuilder ans = new StringBuilder();
        for(int i=0; i<S.length(); i++) {
            char ch = S.charAt(i);
            if(ch == '(') {
                if(stack.size() > 0) {
                    ans.append(ch);
                }
                stack.push(ch);
            } else {
                if(stack.size() > 1) {
                    ans.append(ch);
                }
                stack.pop();
            }
        }
        return ans.toString();
    }
}

Here we don't need a stack, by using count we can easily implement this solution.


Other Posts You May Like
Please leave a comment below if you like this post or found some errors, it will help me to improve my content.

Comments

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Single Number 3 LeetCode Solution - The Coding Shala

LeetCode - Number of Good Pairs Solution - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Java Method Overloading - The Coding Shala