surajkvm007's blog

By surajkvm007, history, 9 years ago, In English

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.

  • Vote: I like it
  • +10
  • Vote: I do not like it

| Write comment?
»
9 years ago, # |
Rev. 3   Vote: I like it +11 Vote: I do not like it

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

  • Sum of all values is 0.
  • There isn't a prefix with negative sum.

OK, now compute L[i] = total sum of elements from index 1 to i. So for each left index l that is an open parenthesis (value 1), find with binary search maximum possible right index r such that there isn't an index i between l and r with L[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 indexes i between l and r such that L[i] = L[l] - 1. You can do this one with binary search too, for example by storing positions for given sum s in a vector Pos[s].

Overall complexity of the algorithm is O(NlogN) if you precompute values with a sparse table or O(Nlog2N) if you use segment tree during the binary search.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    nice

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for explaination

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I am so sorry for necroposting, but I can't help not posting an alternate cleaner solution which is inspired from the Editorial for 1976D - Invertible Bracket Sequences.

      Please go through this problem and it's editorial. You may also go through my submission for the same problem, IIRC I added a comment which may help you if you face difficulty at any point.

      This code prints the number of balanced substrings of a bracket sequence which itself may or may not be balanced.

      Code:
      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I saw the editorial and I think it has the same solution but in the editorial it was not clear for me why the condition p[i] >= p[l-1] should hold

»
9 years ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

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]=='('){

v.push_back(1);

}

else{

int count = 0;

 while(v.top()!=1){

     v.pop_back();

     count++;

  }

v.pop_back();

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

v.push_back(0);

}

}

int n =v.size();

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

v.clear();

cout<<ans<<endl;

Time complexity will be O(N)

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

C++ code : 
        string s;
	cin >> s;
	int result = 0;
	for (int i = 0; i < s.size(); ++i){
		int counter = 0;
		for (int j = i;counter >= 0 &&  j < s.size(); ++j){
			if (s[j] == '(')counter++;
			else counter--;
			if (counter == 0) result++;
		}
	}
	cout << result << endl;
»
9 years ago, # |
  Vote: I like it +14 Vote: I do not like it
I think there is an O(n) solution.
First you can find all the opening parenthesis for closing ones using stack in O(n).
Use array d[n+1] for keeping the count initialized with 0. 
Then for every opening closing pair with opening at i and closing at j set 
d[j] = 1 + d[i-1]. This can be done for all indices from 1 to n in O(n). 
Finally for answer accumulate all d[i]'s.

For example s =    ( ) ( ( ) ) ( ) ( ( ) ( ) ). 
            d = {0,0,1,0,0,1,2,0,3,0,0,1,0,2,4};

So, the answer will be 14.
  • »
    »
    5 months ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    can you also find an efficient way to say if we reverse any substring will it be valid , given the input is not necessarily initially valid

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      if you would have send this 8 years ago then maybe...

»
5 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

We can do this , lets define the level of 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 .

#/*
	AUTHOR:shivam51
	IIESTS
*/
  #include<bits/stdc++.h>
  using namespace std;
  //
  #define add accumulate
  #define ll long long int
  #define rep(i,k,n) for(int i=k;i<n;i++)
  //
  //
	void solve(){
		string str;
		cin>>str;
		ll cnt=0;
		vector<char> vec;
		vll arr(str.length()/2+1,0);
		int pre=0;
		rep(i,0,str.length()){
			if(str[i]=='('){
				++pre;
				vec.pb('(');
			}
			else{
				++cnt;
				vec.pop_back();
				cnt+=arr[pre];
				arr[pre]++;
				--pre;
			}
		}
		cout<<cnt;
	}
  int main(){ 
	hs;
	ll t;
	// cin>>t;
	t=1;
	while(t--)
	    solve();
	return 0; 
} 
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is an incorrect approach. Correct answer for the string $$$(()())(()())$$$ is $$$9$$$ while your code gives output $$$13$$$.