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.

Algorithm Steps:

• Initialize an empty string (result) to store the modified string.
• Initialize a variable (depth) to keep track of the depth of parentheses.
• Iterate through each character of the given string:
• If the character is an opening parenthesis ( and the depth is greater than 0, add it to the result.
• If the character is a closing parenthesis ) and the depth is greater than 1, add it to the result.
• Update the depth based on the current character.
• Return the result string.

Below is the code implementation of the above approach:

C++ Java Python C#

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

string removeOuterParentheses(string s) {
    string result = "";
    int depth = 0;

    for (char c : s) {
        if(c == '(') {
            if(depth > 0){
                result += c;
            }
            depth++;
        } else{
            depth--;
            if(depth > 0) {
                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 without using stack
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) {
        int depth = 0;
        StringBuilder result = new StringBuilder();

        for (char c : s.toCharArray()) {
            if (c == '(') {
                if (depth > 0) {
                    result.append(c);
                }
                depth++;
            } else {
                depth--;
                if (depth > 0) {
                    result.append(c);
                }
            }
        }

        return result.toString();
    }
}

# Python code to remove outermost parenthesis 
# without using stack
def remove_outer_parentheses(s):
    result = ""
    depth = 0

    for c in s:
        if c == '(':
            if depth > 0:
                result += c
            depth += 1
        else:
            depth -= 1
            if depth > 0:
                result += c

    return result

# Example usage
input_str = "(()())(())"
output_str = remove_outer_parentheses(input_str)

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

// C# code implementation to remove 
// outermost parenthesis without using stack
using System;

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)
    {
        string result = "";
        int depth = 0;

        foreach (char c in s)
        {
            if (c == '(')
            {
                if (depth > 0)
                {
                    result += c;
                }
                depth++;
            }
            else
            {
                depth--;
                if (depth > 0)
                {
                    result += c;
                }
            }
        }

        return result;
    }
}

Output:

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

• Time Complexity: We are traversing the given input string only once so the time complexity will be O(n) where n is the length of the given string.
• Space Complexity: We are not using any extra space except the result string which we are using only to store our answer so the overall space complexity is O(1).

Delete Middle Element of Stack.

Given a stack of integers. The task is to delete the middle element from the stack without using extra space. The middle element is defined as the element at position (size of stack / 2 +1). Write a function/method that takes the stack as input and modifies it to delete the middle element.

Example:

Input:  [1, 2, 3, 4, 5]

Output: [1, 2, 4, 5]

Explanation: The middle element is 3, and after deletion, the stack becomes [1, 2, 4, 5].

Input:  [10, 20, 30, 40, 50, 60]

Output: [10, 20, 30, 50, 60]

Explanation: The middle element is 40, and after deletion, the stack becomes [10, 20, 30, 50, 60].

It is very easy to delete the middle element of the given stack by using any extra data structure. Still, the main challenge of this problem is to solve this without using any additional space. Actually, that is also quite simple if our powerful programming tool known as recursion. Before moving to the recursive solution to delete the middle element of the stack. Let's check a simple brute-force solution for this.

Brute Force Approach to Delete Middle Element of Stack.

In this approach, we will use another auxiliary stack or a list to store the given stack element until we reach the middle element and then we will remove (pop) the middle element from the stack and then push back all the elements of the auxiliary stack back to the main stack.

Algorithm Steps:

• Create a stack auxStack to temporarily store elements.
• Calculate the position of the middle element (middle = size / 2 +1).
• Iterate over the first half of the original stack (up to the element just before the middle) and Push each element to the auxStack and pop it from the original stack.
• Skip the middle element of the stack and pop it from the original stack.
• Pop elements from the auxStack and push them back to the original stack.

Below is the code implementation of the above approach:

C++ Java Python C#

// C++ code implementation to delete middle element of stack
// Brute force approach using extra space
#include <iostream>
#include <stack>
using namespace std;

// Function to delete the middle element of a stack without recursion
void deleteMiddle(stack<int>& s) {
    int size = s.size();
    int middle = size / 2 + 1;

    stack<int> auxStack;

    // Push the first half of elements to the auxiliary stack
    for (int i = 0; i < middle - 1; i++) {
        auxStack.push(s.top());
        s.pop();
    }

    // Skip the middle element
    s.pop();

    // Push the elements back to the original stack
    while (!auxStack.empty()) {
        s.push(auxStack.top());
        auxStack.pop();
    }
}

// Function to print the stack
void printStack(stack<int> s) {
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
    cout << endl;
}

int main() {
    // Example usage
    stack<int> myStack;

    // Push elements onto the stack
    myStack.push(1);
    myStack.push(2);
    myStack.push(3);
    myStack.push(4);
    myStack.push(5);

    cout << "Original Stack: ";
    printStack(myStack);

    // Delete the middle element without recursion
    deleteMiddle(myStack);

    cout << "Stack after deleting middle element: ";
    printStack(myStack);

    return 0;
}

// Java code implementation to delete middle element of stack
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack<Integer> myStack = new Stack<>();

        // Push elements onto the stack
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        myStack.push(4);
        myStack.push(5);

        System.out.println("Original Stack: " + myStack);

        // Delete the middle element without recursion
        deleteMiddle(myStack);

        System.out.println("Stack after deleting middle element: " + myStack);
    }

    // Function to delete the middle element of a stack without recursion
    public static void deleteMiddle(Stack<Integer> s) {
        int size = s.size();
        int middle = size / 2 + 1;

        Stack<Integer> auxStack = new Stack<>();

        // Push the first half of elements to the auxiliary stack
        for (int i = 0; i < middle - 1; i++) {
            auxStack.push(s.pop());
        }

        // Skip the middle element
        s.pop();

        // Push the elements back to the original stack
        while (!auxStack.isEmpty()) {
            s.push(auxStack.pop());
        }
    }
}

# Python code to delete middle element of stack
def delete_middle(s):
size = len(s)
middle = size // 2 + 1

aux_stack = []

# Push the first half of elements to the auxiliary stack
for i in range(middle - 1):
    aux_stack.append(s.pop())

# Skip the middle element
s.pop()

# Push the elements back to the original stack
while aux_stack:
    s.append(aux_stack.pop())

# Example usage
my_stack = [1, 2, 3, 4, 5]

print("Original Stack:", my_stack)

# Delete the middle element without recursion
delete_middle(my_stack)

print("Stack after deleting middle element:", my_stack)

// C# code implementation to delete middle element of stack
using System;
using System.Collections.Generic;

class MainClass {
    public static void Main(string[] args) {
        Stack<int> myStack = new Stack<int>();

        // Push elements onto the stack
        myStack.Push(1);
        myStack.Push(2);
        myStack.Push(3);
        myStack.Push(4);
        myStack.Push(5);

        Console.WriteLine("Original Stack: " + string.Join(" ", myStack));

        // Delete the middle element without recursion
        DeleteMiddle(myStack);

        Console.WriteLine("Stack after deleting middle element: " + string.Join(" ", myStack));
    }

    // Function to delete the middle element of a stack without recursion
    public static void DeleteMiddle(Stack<int> s) {
        int size = s.Count;
        int middle = size / 2 + 1;

        Stack<int> auxStack = new Stack<int>();

        // Push the first half of elements to the auxiliary stack
        for (int i = 0; i < middle - 1; i++) {
            auxStack.Push(s.Pop());
        }

        // Skip the middle element
        s.Pop();

        // Push the elements back to the original stack
        while (auxStack.Count > 0) {
            s.Push(auxStack.Pop());
        }
    }
}

Output:

Original Stack: 5 4 3 2 1
Stack after deleting middle element: 5 4 2 1

• Time Complexity: O(n) where n is the number of elements present in the given stack.
• Space Complexity: O(n) as we are using an extra stack to delete the middle element of the stack.

Delete Middle Element of the Stack Using Recursion.

We can delete the middle element of the stack using recursion without using any extra space. In this approach, we will recursively pop the stack element, and while unwinding we will push back all the elements except the middle element.

Algorithm Steps:

• The base case of our recursive call is when our stack gets empty.
• Pop an element from the stack and recursively call the function.
• While unwinding from the recursive calls, increment a counter to keep track of the number of elements.
• If the counter indicates the middle element, skip pushing it back onto the stack.
• While unwinding, push the elements back onto the stack.

Below is the code implementation of the above recursive approach:

C++ Java Python C#

// C++ code for recurisvely delete middle element of stack
#include <iostream>
#include <stack>

using namespace std;

// Function to delete the middle element of a stack using recursion
void deleteMiddle(stack<int>& s, int current, int middle) {
    // Base case: stack is empty
    if (s.empty()) {
        return;
    }

    // Recursive call: pop an element and make a recursive call
    int temp = s.top();
    s.pop();
    deleteMiddle(s, current + 1, middle);

    // Count elements and skip pushing the middle element
    if (current != middle) {
        s.push(temp);
    }
}

// Function to print the stack
void printStack(stack<int> s) {
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
    cout << endl;
}

int main() {
    stack<int> myStack;

    // Push elements onto the stack
    myStack.push(1);
    myStack.push(2);
    myStack.push(3);
    myStack.push(4);
    myStack.push(5);

    cout << "Original Stack: ";
    printStack(myStack);

    int middle = myStack.size() / 2;
    
    // Delete the middle element using recursion
    deleteMiddle(myStack, 0, middle);

    cout << "Stack after deleting middle element: ";
    printStack(myStack);

    return 0;
}

import java.util.Stack;

public class Main {
  public static void main(String[] args) {
      Stack<Integer> myStack = new Stack<>();

      // Push elements onto the stack
      myStack.push(1);
      myStack.push(2);
      myStack.push(3);
      myStack.push(4);
      myStack.push(5);

      System.out.println("Original Stack: " + myStack);

      int middle = myStack.size() / 2;

      // Delete the middle element using recursion
      deleteMiddle(myStack, 0, middle);

      System.out.println("Stack after deleting middle element: " + myStack);
  }

  // Function to delete the middle element of a stack using recursion
  public static void deleteMiddle(Stack<Integer> s, int current, int middle) {
      if (s.isEmpty()) {
          return;
      }

      int temp = s.pop();
      deleteMiddle(s, current + 1, middle);

      if (current != middle) {
          s.push(temp);
      }
  }
}

# Python program to delete middle element of stack using Recursive

def delete_middle(s, current, middle):
# Base case: stack is empty
if not s:
    return

# Recursive call: pop an element and make a recursive call
temp = s.pop()
delete_middle(s, current + 1, middle)

# Count elements and skip pushing the middle element
if current != middle:
    s.append(temp)

# Example usage
my_stack = [1, 2, 3, 4, 5]

print("Original Stack:", my_stack)
middle = len(my_stack) // 2

# Delete the middle element using recursion
delete_middle(my_stack, 0, middle)

print("Stack after deleting middle element:", my_stack)

//C# code to delete middle element of stack using Recursion
using System;
using System.Collections.Generic;

class MainClass {
    public static void Main(string[] args) {
        Stack<int> myStack = new Stack<int>();

        // Push elements onto the stack
        myStack.Push(1);
        myStack.Push(2);
        myStack.Push(3);
        myStack.Push(4);
        myStack.Push(5);

        Console.WriteLine("Original Stack: " + string.Join(" ", myStack));

        int middle = myStack.Count / 2;

        // Delete the middle element using recursion
        DeleteMiddle(myStack, 0, middle);

        Console.WriteLine("Stack after deleting middle element: " + string.Join(" ", myStack));
    }

    // Function to delete the middle element of a stack using recursion
    public static void DeleteMiddle(Stack<int> s, int current, int middle) {
        if (s.Count == 0) {
            return;
        }

        int temp = s.Pop();
        DeleteMiddle(s, current + 1, middle);

        if (current != middle) {
            s.Push(temp);
        }
    }
}

Output:

Original Stack: 5 4 3 2 1 
Stack after deleting middle element: 5 4 2 1 

• Time Complexity: O(n) where n is the number of elements in the stack.
• Space Complexity: O(n) using auxiliary space for Recursion.