Take a freq array and initialize to zero. This array stores 1 for an index i if (i,i+1,i+2) is rich, otherwise stores 0.
Approach is for given l,r we need to check if any one index in freq array in range[l,r-2] is one. Then the substring will be rich.
To check this we store the sum of first i positions in ith location,i.e ai = a0+a1+a2+…+ai
So we need to check a(l)+a(l+1)+…+a(r-2) is greater than zero or not. (Since if any one element is 1 ,substring is rich)
We can get the sum in O(1) time by subtracting freq[r-2] - freq[l-1].
Example:
For s= “helloworld”
Freq={0,0,1,2,2,3,3,3,3,3,3}
Now Q1: l=1 r=3
freq[3-2]-freq[0]=0
And: NO
U can check for other queries.
Overall it takes O(N+Q) time.
3 Likes
but why u did it,tell me what is the meaning of freq[i] denotes…
It basically denotes any substring starting with ith position is rich or not
Segment Tree/Sparse Table are overkill and the same thing (with similar complexity) can be achieved by simply storing the starting indices of all rich sub-strings of length 3 and given a query check if any index lies in the l to r range which can be achieved by applying lower_bound on the indices array and checking if it is ≤ r-2.
Here’s the code for the same: CodeChef: Practical coding for everyone
Complexity can be further reduced to O(N+Q) as pointed out in the comments above
3 Likes
why freq[r-2]+freq[l-1] is done why not freq[r]
please explain why don’t we check for substring of length greater than 3.
When u are checking freq[r-2] u are checking the substring starting from position r-2 and ending at r. (Since base case is substring with length 3) 
If u check freq[r] u will be checking substring with position r,r+1,r+2 which is outside range [l,r] and also out of bounds for r>n-2
It’s explained in the editorial itself
In other words, it’s not possible to have a longer rich substring without having a smaller 3-length rich substring in it. So it’s enough to check for substrings of length 3 as any rich substring must be made up of at least one of these.
Can you tell me why I am getting TLE for this submission : CodeChef: Practical coding for everyone .
It answers each query in O(1) time and take O(n) time to pre-process. Total time-complexity is O(n * t + q * t). I am not able to figure out why I am getting a TLE.
Try || instead of && in line 56
it still gives wrong answer? but why || will be true since both condition should be true for YES.
I agree that instead of segtree prefix sums are better in this particular problem but for the bonus or problems similar to the bonus you might encounter somewhere else segment trees are required.
3 Likes
Bro, I have done exactly the same thing, but am getting WA . I have checked many test cases. Will you plz check my code once.
https://www.codechef.com/viewsolution/26024140
I’ll give you a hint : Line 59 
I can’t really spot any mistake other than the array size of count. But when I was trying to compile the program sometimes it was showing some errors, and sometimes working properly. I don’t know much java and thus why that was happening. Do check the count array size anyway. Logically it looks correct to me.
Yess, I changed the count size still it did not work. If anyone can find the problem other than array size of count, then plz tell. BTW thank you derco .
I think newtech66 is checking for every digit, so that guarantees checking the left and the right. Say there is a string “aaaabc”. It is rich. “aaa” is rich and “abc” is not. Using a boolean array will give you something like this[true, true, true, false, false, false], meaning at i-th position, the substring string[i:i+2] is rich
Why rating for august cook-off is not revealed till now??