Remove Outermost Parentheses

Problem Link:

https://leetcode.com/problems/remove-outermost-parentheses/description/

Solution:

Using Stack:

We will use the algorithm similar to find valid paranthesis:

1. Create a stack

2. Push s[0]

3. Declare an 'ind' variable and initialize it to 0

4. Run a loop from 1 to n-1.

5. if st.top() == '(' and s[i]==')' ---- > Pop the stack

6. else ----> push s[i] to stack

7. if at any moment st.empty()==true

   1. result += s.substr(ind+1,i)

   2. ind = i+1

8. Return result

// TIME COMPLEXITY : O(N)
// SPACE COMPLEXITY : ~ O(N)
class Solution {
public:
    string removeOuterParentheses(string s) {

        int n = s.size();
        stack<int> st;

        st.push(s[0]);
        string output = "";

        int ind = 0;
        for(int i=1;i<n;i++){

            if(!st.empty() && st.top()=='(' && s[i]==')'){
                st.pop();
            }
            else{
                st.push(s[i]);
            }

            if(st.empty()){
                for(int j=ind+1;j<i;j++){
                    output+=s[j];
                }

                ind = i+1;
            }
        }
        return output;
    }
};

---

Without using extra space:

1. Maintain a variable count to keep track of the current nesting level of parentheses.

2. When encountering an opening parenthesis '(' and the count is 0, increment the count and ignore adding this parenthesis to the result since it's the outermost one.

3. When encountering an opening parenthesis '(' and the count is greater than or equal to 1, increment the count and append the parenthesis to the result. This represents an inner parenthesis.

4. When encountering a closing parenthesis ')' and the count is greater than 1, append the parenthesis to the result and decrement the count. This represents an inner parenthesis.

5. When encountering a closing parenthesis ')' and the count is exactly 1, decrement the count without appending to the result, as it represents the outermost closing parenthesis.

6. Return result

// TIME COMPLEXITY: O(N)
// SPACE COMPLEXITY: O(1)

class Solution {
public:
    string removeOuterParentheses(string s) {

        int n = s.size();

        string ans = "";
        int count = 0;

        for(int i=0;i<n;i++){

            if(s[i]=='(' && count==0){
                count++;
            }
            else if(s[i]=='(' && count>0){
                ans+=s[i];
                count++;
            }
            else if(s[i]==')' && count>1){
                ans+=s[i];
                count--;
            }
            else if(s[i]==')' && count==1){
                count--;
            }
        }

        return ans;
    }
};