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.