balanced parenthesis

Revision en1, by surajkvm007, 2016-03-22 18:34:54

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.

Tags substring, parenthesis, balanced

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English surajkvm007 2016-03-22 18:34:54 432 Initial revision (published)