# How to solve Rich Substring(RICHSTR) from August 19 Cook-Off?

Can anybody please share their approach?

1 Like

I was going for
`if s[i] == s[i+1] or s[i] == s[i+2]`
but that failed, idk why.
Every rich substring will satisfy this. Some examples:
aab , aba, abb
aaab, â€¦
ababa,abbaa, â€¦

1 Like

Me too. I checked for contiguous ones only, and it failed.

1 Like

1 Like

Looking forward to it!

Yupp waiting for announcement also this might be unrated contest

what about if s[i+1]==s[i+2]? Including that, and keeping a list of the starting indexes of the 3-length rich strings should do the job.

Thatâ€™s unfortunate, given that I somehow got a somewhat respectable rank(82) lol. Iâ€™m such a noob. XD

i donâ€™t think rated or unrated is such a big deal. just improve

4 Likes

Though the idea seems correct, but I think it would still fail because of TLE, correct me If I am wrong but using this approach requires traversing the substring between L to R. Doing this for each query would result into a run time complexity of `O(N^2)` in the worst case. While the constraints only permit a complexity of O(N*log(N)).
Correct me If I am wrong.

1 Like

I got a WA instead of a TLE. So, something fishy is going onâ€¦

1 Like

Yes, right now I was trying to do just that.
Can anyone point out the error in this?
https://www.codechef.com/viewsolution/26015287

I didnâ€™t read the question carefully and assumed that we have to return the max length of the valid substringâ€¦wasted a lot of time

Yup. My bruteforce like approach got TLE.

â€śYESâ€ť and â€śNOâ€ť, not â€śYesâ€ť and â€śNoâ€ť

1 Like
1. It should be r-l<3
2. You need to run two loops separately till n-2 and n-3 so that you donâ€™t access array values out of bound.
3. This will timeout because itâ€™s O(n*q)

NVM at least you tried. Too bad, I couldnâ€™t realize this simple thing(since you want a character to repeat more than N/2 times, therefore one such character must always occur at alternate positions(and at contiguous positions at least once). I am such a noob

1 Like

Yeah that applies to codechef as well

1 Like

For a character to be a majority character in a string, it definitely shall be a majority element in a substring of size 3. So, I create a count table to calculate count of each character in the prefix till index i. Then for each substring of size 3, I find if there is an element that appears more than once. Incase there is such element, I increment prefix count. This prefix count stores the number of valid length 3 substrings with a majority element till index i.
Now, for each query, in O( 1 ), we can check if there is any substring of length 3 between l to r with a majority element by comparing prefix[r] and prefix[l + 1]( because prefix[l + 2] will store a substring of length 3 starting from index l.
My submission: https://www.codechef.com/viewsolution/26015383 (Didnâ€™t give contest but yeah)

3 Likes

I had thought of checking the substring of size 3 onlyâ€¦but okay wow didnâ€™t think so much ahead!
Thanks a lot XD