Can anybody please share their approach?
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
Me too. I checked for contiguous ones only, and it failed.
Editorial will be uploaded soon
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
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.
I got a WA instead of a TLE. So, something fishy is going on…
Yes, right now I was trying to do just that.
Can anyone point out the error in this?
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”
- It should be r-l<3
- You need to run two loops separately till n-2 and n-3 so that you don’t access array values out of bound.
- 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
Yeah that applies to codechef as well
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)
I had thought of checking the substring of size 3 only…but okay wow didn’t think so much ahead!
Thanks a lot XD