The following question was asked to my friend in an interview : given a string consisting only of '(' and ')'. find total number of substrings with balanced parenthesis Note: the input string is already balanced.

The only solution i can think of this problem is brute force which takes n^3 time. Is there a faster solution possible.If there is then i would also like to know the build up to that approach.

Consider open parenthesis as 1 and closing parenthesis as -1, so necessary conditions for substring to be balanced are:

OK, now compute

L[i] = total sum of elements from index 1 toi. So for each left indexlthat is an open parenthesis (value 1), find with binary search maximum possible right indexrsuch that there isn't an indexibetweenlandrwithL[i] <L[l] - 1. This ensures condition 2. You can do this step with a segment tree or a sparse table. Now to satisfy condition 1, find all indexesibetweenlandrsuch thatL[i] =L[l] - 1. You can do this one with binary search too, for example by storing positions for given sumsin a vectorPos[s].Overall complexity of the algorithm is

O(N_{log}N) if you precompute values with a sparse table orO(N_{log2}N) if you use segment tree during the binary search.raigus in the comment section below gave a linear approach!

nice

Can anybody tell If my approach is right or not ?

C++ code

string s;

cin>>s;

int ans = 0;

vector v;

for(int i =0;i<s.length();i++){

if(s[i]=='('){

}

else{

}

}

int n =v.size();

ans += n*(n+1)/2;

v.clear();

cout<<ans<<endl;

Time complexity will be O(N)

runs in linear time, Holy sh#t!

")()(" gives 6 seems wrong. I had to add a few v.empty() checks to prevent the code from top/pop on an empty stack.

You are just 4 years late.

Yeah, just stumbled on this problem. Still wonder if there is a valid O(n) solution.

Ok then, cool

if the length of string is not large you can use a simple O(n^2) solution .

We can do this , lets define the

levelof any "()" to be the number of opening brackets under which it appears so just count number of "()" and for every "()" also add in the answer the number of balanced substrings appearing in that level .This is an incorrect approach. Correct answer for the string $$$(()())(()())$$$ is $$$9$$$ while your code gives output $$$13$$$.

yes

~~~~~

~~~~~