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?
Please Help.
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)