The Killjee and Kth letter problem stated that |S|<=2.10^5 .
But there was no test case containing a string of 2.10^5 same characters . ( Not even > 2*10^4 characters).
Many or maybe most solutions thus had passed the test cases. Even my solution https://www.codechef.com/viewsolution/17032732 passed with an AC in 0.1s. I had run my solution for a test case, where the string consisted of 'a’s only and its length was 10^5. My solution ran out of time for the same. Also I have run a few more submitted solutions, which too ran out of time or gave Runtime Errors.
I was doubtful of my solution passing the test cases, which surprisingly did when I submitted the final code. Some users might have wasted their time too in thinking over a better solution, and some might not even have submitted their code thinking that it won’t fetch them an AC.
There was a testcase with only 2 characters with probability of 2nd character to appear being 1/10000.
EDIT: The case you are talking about is very easy to get rid of just print the only letter in string. So,it wouldn’t had stopped your solution getting ac
This is an AC solution https://www.codechef.com/viewsolution/17000927
When I run this soln on array length 2*10^5 with all a’s,and b’s are occuring at every 10000th index, it gives TLE.
https://www.ideone.com/KBhk3v
P.S. It rather also gives a TLE even when I run it on all a’s and even when length is 10^4 with second character occuring at every 1000th index. The same is with my solution. This could have let to confusion, hence many might not even have submitted their code. I had tried it on few more solutions, hence I had posted this.
@killjee Also you can do randomly appearing ‘a’ and ‘b’ which will be totally impossible to handle. Or 10^5 ‘a’ then 10^5 ‘b’, and things like that. I find it really unfair to not test for those test cases, as I haven’t coded my solution because I knew it would TL on these tests, so I tried to find a solution which passes these too. But as it turns out there were no test cases for these pretty straight forward corner cases, which seems pretty inconsiderate.
What will you say about building suffix array in O(|S|^2)? It’s amazing 
