### pritishn's blog

By pritishn, 5 weeks ago, You are given a binary string (consisting of 0,1) and you can rotate the string in any order. Basically if the string is s1s2s3...s(n-1)s(n) , you can make it s2s3s4,,,s(n-1)s(n)s1 .

Print out the rotation which has the maximum value in binary representation.

For example:
s=0110
ans= 1100

|s| <= 10^5

Can anyone suggest any approach ? I'm unable to think of any fast approach. Comments (18)
 » It's similiar to this one i guess.
•  » » Oh..thanks. But it had no explanation for it's editorial.
•  » » » 5 weeks ago, # ^ | ← Rev. 4 →   Make a new string $x = s + s$ Replace all '1' by 'z' and all '0' by 'a'. Find largest lexicographic sub-string of size $n$ in string $x$ using the concept mentioned here : https://codeforces.com/blog/entry/75953When you finally find the required substring , print it till length-'n' only
•  » » » There is an exact question on Hackerearth same as yours and has linear solution but i can't find it now. But we can solve it using binary search to find lexographically largest prefix(using rolling hash).
 » This may be overkill, but it shouldn't be hard with a suffix tree.
•  » » Thanks. Looks like it's time to finally study suffix array and tree. :P
•  » » » One can also use a suffix array in the same way.
 » You can use this:Take the complement of the string run the algorithm and then take the complement again.
•  » » Thanks for the link!
 » 5 weeks ago, # | ← Rev. 4 →   We can maintain the binary representations of each prefix and suffix of the string. Then for each position, calculate what will be the result in binary if that position was the first one.Eg — s = 0110pref vals = 0 1 3 6suff vals = 6 6 2 0then for the indices we have 0th — 61st — 12 = (6x2 + 0)2nd — 9 = (2*4 + 1)3rd — 3 = (0*8 + 3)Hence answer is 12 (1100). Complexity should be O(n)
•  » » The string has length upto 10^5. Calculating actual decimal value will be not possible.
•  » » » Oh yeah you are right.
 » 5 weeks ago, # | ← Rev. 3 →   Replace 0 with a and 1 with b and then duplicate the string and find suffix array, answer is last value in the array.
•  » » funny coincidence: problem asked in blog post is same problem as the first example problem in the stanford suffix array pdf: http://web.stanford.edu/class/cs97si/suffix-array.pdf
 » to compare to 2 possible choices.binary search for the first i such that first (i-1) characters of both choices are same and ith character is different.this can be done with hashing.you need to do this n-1 times so O(nlogn)
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   .
 » count the largest group of ones in the cyclic string and rotate till largest group of ones comes to the start of the string .
 » What you are looking for is lexicographically maximum cyclic shift of binary string. Link This should help.