Concurrently Balanced Strings (USACO November 2012 Gold)

Problem, Solution

I am confused about the solution in Concurrently Balanced Strings. Could someone please explain what the variables lft, L, R, and mp are used for, and give a slightly more detailed explanation of the solution in general?



This is a pretty standard technique when dealing with parenthesis(but definitely non trivial initially). The idea is to turn all ( to 1 and all ) to -1. With this, we can create a prefix sums array on the entire bracket sequence. Notice that in order for a contiguous interval of brackets, [start, end], to be valid, it must satisfy two conditions: prefix[i] >= 0 for all start <= i <= end, and prefix[start] = prefix[end]. If you’re still confused you can search for brackets problems on leetcode(that’s where I learned this technique). With the above observation in mind it’s not difficult to come up with a solution via maps, which is what the sol uses.