Google Apac 2017 Round B Problem A "Sherlock and parentheses"

The problem was to find maximum number of substrings of L left brackets and R right brackets that are balanced. The first thing we can see is that, the number of balanced substrings will be maximized only when the left and right appear in pair, without any nesting. .i.e.

   ()()()()()()()()()()()()

as L and R are not same. We need to find minimum of L and R, and then count the number of sub-strings, which is given by n*(n+1)/2, where n is min(L,R).

Here is python code for the same.

Please subscribe to the blog, share the post if you like it. Leave a comment about mistakes in blog post, problems you would like to solve, get help on. Let us know if you have any other feedback about the blog.