I would like to comment to the post below by abulatovic. I solved this problem a few minutes ago, and I agree, it is not an easy one, but from my perspective, the challenge is mostly in getting all the border cases right. I did not use a "maxheap" or a "maxsegment tree" (I do not even know what they are, but I did not use any trees). In my first two submissions, which did not pass all test cases, it was never that I ran into timeouts, but rather either wrong answers (due to some mistakes in formulas) or segmentation faults (not checking things enough). Anyway, do not get onto the wrong track - the problem is well solvable. Obviously you cannot traverse the string again for every rotation, or effectively rotate the string without running into performance problems.