String Question

Revision en2, by bablu_45, 2019-09-27 23:49:30

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

1) Choose an index 'i' greater than the previous index 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^5

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 "axad".

Now choose suffix from index 1 and rotate the string "xad" 1 time to the left to obtain "adx". Final string is "aadx".

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English bablu_45 2019-09-28 14:33:12 8
en5 English bablu_45 2019-09-28 00:47:32 2 Tiny change: 'tring<=10^5\n\nExampl' -> 'tring<=10^3\n\nExampl'
en4 English bablu_45 2019-09-28 00:00:34 22
en3 English bablu_45 2019-09-27 23:51:55 26
en2 English bablu_45 2019-09-27 23:49:30 6 Tiny change: ' left or rotations' -> ' left or right rotations'
en1 English bablu_45 2019-09-27 23:48:19 990 Initial revision (published)