My solution was O(|S|) have a look…
https://www.codechef.com/viewsolution/18070826
… let’s say string is abbaabb so
I stored 1 0 -1 0 1 0 -1 in an array and computed the ans with ceiling function…
basically I calculated that for how many repetition each character will contribute…
1 Like
Good job 
In tester’s O(SlogS) solution, why vector “have” is sorted?
Refer to O(|S|) solution for now. While trying to explain, I noticed @admin linked the wrong solution there. She linked the O({S}^{2}) solution there, I will get that fixed. Sorry for the inconvenience 
I also used binary search with prefix sum array. and then simple loop.
I guess less and simple code
https://www.codechef.com/viewsolution/18606690