bablu_45's blog

By bablu_45, history, 5 years ago, In English

Given a string 's', we can perform the following operation:-

1) Choose an index 'i' greater than the index chosen in previous operation and rotate the suffix(left or right rotate) formed from i, any number of times.

What is the minimum number of operations required to make smallest possible lexicographical string from s?

Size of input:- length of string<=10^3

Example:-

1) s:- acab

Choose suffix from index 1 and right rotate the string "cab" 2 times to the right to obtain "aabc" which is the smallest possible lexicographical string.

So the minimum number of operations required is 1.

2) s:- cdax

First, choose suffix from index 0 and rotate the string "cdax" two times to the right to get "axcd".

Now choose suffix from index 1 and rotate the string "xcd" 1 time to the left to obtain "cdx". Final string is "acdx".

So minimum number of operations required is 2.

Note:- In a single operation you can perform any number of left or right rotations on a suffix.

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

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think in example 2, the final string should be "acdx".

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

As |S|<=1000 , So it can be done by bruteforce easily.

1) You have to start a loop for(i=0;i<n;i++).

2) for(j=i;j<n;j++)

3) Let first appearance of the samllest character for all respective j is x, and the last appearance of the smallest character for all respective j is y.

4) If n-y+1<x-j , you have to rotate it right n-y+1 times.

5) Else, you have to rotate it left x-j times;

6) You have to count++ always when rotating a suffix, You will get the final string and the count.

Note:-For rotating a string visit https://www.geeksforgeeks.org/left-rotation-right-rotation-string-2/

Please share the problem link so that I can also submit it.

Hope it helps :)

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

    Your greedy approach will fail for strings where there are multiple smallest character on the right. Smallest number of operations depends on which of them you choose.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Our first observation is that we will always sort the string in lexicographical order. It is just a matter or minimizing the number of operations.

Consider an index 'i'. For every character currently to the right of i, we have to find which element, when rotated next to i (left or right doesn't matter) will give us the least lexicographical suffix. By doing so, we will minimize the operations we need to make later on because characters are in their respective places in advance.