Boring_Day's blog

Help me Solve this problem
By Boring_Day, history, 2 years ago, In English

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.

  • Vote: I like it
  • -15
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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)

→ Reply