Flipkart SDE - 1

Given a balanced expression, find if it contains duplicate parenthesis or not. A set of parenthesis are duplicate if the same subexpression is surrounded by multiple parenthesis

Below expressions have duplicate parenthesis -
((a+b)+((c+d)))
The subexpression "c+d" is surrounded by two
pairs of brackets.

Below expressions don't have any duplicate parenthesis -
((a+b)+(c+d))
No subexpression is surrounded by duplicate
brackets.

: Here the problem is of standard stack problem , let us dry run and understand it ::

Initially My string is ((a+b)+((c+d)))
Step 1:Push all char if it is not ')'
my stack [((a+b]
step 2:Now my string is at ')' , Here the idea is we need to check is there any character except '(' i between prev '(' and present , if the count is 0 , then we can say it is duplicate...

#include <bits/stdc++.h>

using namespace std;

int main(){
    string s;
    cin >> s;
    stack<char>st;
    for(int i = 0;i < s.size();i++){
        if(s[i] == ')'){
            int count = 0;
            int pres = st.top();
            st.pop();
            while(pres != '('){
                pres = st.top();
                st.pop();
                count++;
            }
            if(count < 1){
                cout << "Duplicate Exists" << endl;
                return 0;
            }
        }else{
            st.push(s[i]);
        }
    }
    cout << "No Duplicate Exists" << endl;
    return 0;
}
Comments (0)