pritishn's blog

Binary string rotation to produce maximum number?
By pritishn, 4 years 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

Comments Comments (17)
| Write comment?
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

It's similiar to this one i guess.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      4 years 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.net/blog/entry/75953

      When you finally find the required substring , print it till length-'n' only

      → Reply
    • »
      »
      »
      4 years 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).

      → Reply
»
4 years 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.

→ Reply
  • »
    »
    4 years 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

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

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

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

You can use this:Lexicographically minimal string rotation

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

→ Reply
»
4 years 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)

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    The string has length upto 10^5. Calculating actual decimal value will be not possible.

    → Reply
»
4 years 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.

→ Reply
»
4 years 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)

→ Reply
»
4 years 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.

→ Reply