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.

It's similiar to this one i guess.

Oh..thanks. But it had no explanation for it's editorial.

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/75953

When 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:

https://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation#:~:text=In%20computer%20science%2C%20the%20lexicographically,order%20of%20all%20such%20rotations.

Take the complement of the string run the algorithm and then take the complement again.

Thanks for the link!

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 = 0110

pref vals = 0 1 3 6

suff vals = 6 6 2 0

then for the indices we have 0th — 6

1st — 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.

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)

.

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.