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.