pritishn's blog

By pritishn, 5 weeks ago, In English

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.

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

It's similiar to this one i guess.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 4   Vote: I like it +17 Vote: I do not like it

      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

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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).

»
5 weeks ago, # |
  Vote: I like it +22 Vote: I do not like it

This may be overkill, but it shouldn't be hard with a suffix tree.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks. Looks like it's time to finally study suffix array and tree. :P

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      One can also use a suffix array in the same way.

»
5 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it
»
5 weeks ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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)

»
5 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Replace 0 with a and 1 with b and then duplicate the string and find suffix array, answer is last value in the array.

»
5 weeks ago, # |
  Vote: I like it +28 Vote: I do not like it

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, # |
  Vote: I like it -8 Vote: I do not like it

count the largest group of ones in the cyclic string and rotate till largest group of ones comes to the start of the string .

»
5 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

What you are looking for is lexicographically maximum cyclic shift of binary string. Link This should help.