Remove Outermost Parenthesis of Primative String.

Given a string representing a valid parentheses sequence, your task is to remove the outermost parentheses of every primitive pair of parentheses. A primitive pair of parentheses is a pair that is not part of any other parentheses. Implement a function that takes a string as input and returns a modified string with the outermost parentheses removed.

The input string s consists of parentheses characters '(' and ')' only.
The length of s is between 1 and 1000.

Example:

Input: "(()())(())"

Output: "()()()"

Explanation: After removing the outermost parentheses of each primitive pair, the resulting string is "()()()"

Input: "((()(())))"

Output: "(()(()))"

Explanation: After removing the outermost parentheses of each primitive pair, the resulting string is "(()(()))".

There are different approaches to solving this problem of removing outermost parenthesis and here we are going to discuss two of them. Let's see each of these approaches one by one:

Remove the Outermost Parenthesis using Stack.

This approach leverages a stack data structure to keep track of opening parentheses. By iterating through the input string and using the stack to identify pairs of parentheses, the algorithm selectively removes the outermost parentheses, resulting in a modified string without those outermost pairs.

Algorithm Steps:

Initialize an empty stack to keep track of opening parenthesis.
Initialize an empty string (result) to store the modified string.
Iterate through each character of the given input string:
If the character is an opening parenthesis '(' push it onto the stack.
If the character is closing parenthesis ')' pop from the stack and if the stack is not empty after popping then add the character to the result string.
Return the result string.

Below is the code implementation of the above approach:

C++ Java Python C#

// C++ code to remove outermost parenthesis 
#include <iostream>
#include <stack>
using namespace std;

//function
string removeOuterParentheses(string s) {
    stack<char> parenthesesStack;
    string result = "";

    for (char c : s) {
        if (c == '(') {
            if (!parenthesesStack.empty()) {
                result += c;
            }
            parenthesesStack.push(c);
        } else {
            parenthesesStack.pop();
            if (!parenthesesStack.empty()) {
                result += c;
            }
        }
    }

    return result;
}

int main() {
    string input = "(()())(())";
    string output = removeOuterParentheses(input);

    cout << "Original String: " << input << endl;
    cout << "Removing outermost parentheses: " << output << endl;

    return 0;
}

// Java code to remove outermost Parenthesis 
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        String input = "(()())(())";
        String output = removeOuterParentheses(input);

        System.out.println("Original String: " + input);
        System.out.println("Removing outermost parentheses: " + output);
    }

    public static String removeOuterParentheses(String s) {
        Stack<Character> parenthesesStack = new Stack<>();
        StringBuilder result = new StringBuilder();

        for (char c : s.toCharArray()) {
            if (c == '(') {
                if (!parenthesesStack.isEmpty()) {
                    result.append(c);
                }
                parenthesesStack.push(c);
            } else {
                parenthesesStack.pop();
                if (!parenthesesStack.isEmpty()) {
                    result.append(c);
                }
            }
        }

        return result.toString();
    }
}

# Python code to remove outermost parenthesis
def removeOuterParentheses(s):
parentheses_stack = []
result = ""

for c in s:
    if c == '(':
        if parentheses_stack:
            result += c
        parentheses_stack.append(c)
    else:
        parentheses_stack.pop()
        if parentheses_stack:
            result += c

return result

input_str = "(()())(())"
output_str = removeOuterParentheses(input_str)

print("Original String:", input_str)
print("Removing outermost parentheses:", output_str)

//C# code to remove outermost parenthesis
using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        string input = "(()())(())";
        string output = RemoveOuterParentheses(input);

        Console.WriteLine("Original String: " + input);
        Console.WriteLine("Removing outermost parentheses: " + output);
    }

    public static string RemoveOuterParentheses(string s)
    {
        Stack<char> parenthesesStack = new Stack<char>();
        System.Text.StringBuilder result = new System.Text.StringBuilder();

        foreach (char c in s)
        {
            if (c == '(')
            {
                if (parenthesesStack.Count > 0)
                {
                    result.Append(c);
                }
                parenthesesStack.Push(c);
            }
            else
            {
                parenthesesStack.Pop();
                if (parenthesesStack.Count > 0)
                {
                    result.Append(c);
                }
            }
        }

        return result.ToString();
    }
}

Output:

Original String: (()())(())
Removing outermost parentheses: ()()()

Time Complexity: We are traversing the complete string only once so the time complexity will be O(n) where n is the length of the given input string.
Space Complexity: We are using an extra stack to solve the problem and we are also using an extra string just to store our modified string so overall space complexity will be O(n).

Remove the Outermost Parenthesis Without Using Stack.

In this approach, the algorithm maintains a count of the depth of parentheses while iterating through the input string. By intelligently deciding which parentheses to include in the modified string based on their depth, the algorithm effectively removes the outermost parentheses of each primitive pair. This depth-counting approach provides a simple yet efficient solution to the problem.