I was solving yesterday's c with a different approach. To solve it with my technique what i need to know is:
Let's say we have a string 's' of length 'n' with parenthesis ('(' or ')') and we have queries with 'L' and 'R' (1<=L<=R<=N).
we need to tell whether the substring from L to R is balanced or not.
Is there any way to solve the queries in constant time or lets say log(n) time?
Don't ignore :((.
You can store the prefix in array pre. Then make sure that pre[r]-pre[l-1] = 0 and minimum value of pre in [L,R] is >= pre[L-1]. For checking second condition you can use segment tree for O(logn) query or use stack method to precompute next smaller element to query in O(1)