Smallest String After Ordered Operations

Easy
0/40
Average time to solve is 15m
profile
Contributed by
13 upvotes
Asked in company
Deloitte

Problem statement

You are given a string ‘S’ of length ‘N’ and a positive integer ‘K’. You can perform the following operation any number of times on ’S’.

In each operation, you can delete one of the first ‘K’ characters of ‘S’ and append it at the end of the ‘S’.

You have to find the lexicographically smallest string you can obtain by performing any number of operations.

Note:

String ‘p’ is lexicographically smaller than string ‘q’, if ‘p’ is a prefix of ‘q’, is not equal to ‘q’ or there exists ‘i’, such that ‘p[i]’  <  ’q[i]’ and for all ‘j’  <  ’i’ it is satisfied that ‘p[j]’  =  ’q[j]’.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain two space-separated integers  ‘N’ and ‘K’ which denotes the length of ‘S’ and integer ‘K’. 

The second line of each test case will contain a single string ‘S’.
Output Format: 
For each test case, return the lexicographically smallest string obtained by performing any number of operations on ‘S’.
Note: 
You don’t need to print anything; it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 10^3
1<= K <= N
S[ i ] belongs to {a to z}

Time limit: 1 sec
Sample Input 1:
2
5 1
acbaa
3 2
onm
Sample Output 1:
aaacb
mno
Explanation of sample input 1:
In the first test case, 
In the first move we will delete ‘a’ from the beginning and put it at the end, ‘S’ = “cbaaa”.
In the second move we will delete ‘c’ from the beginning and put it at the end, ‘S’ = “baaac”.
In the third move we will delete ‘b’ from the beginning and put it at the end, ‘S’ = ‘aaacb’.

For the second test case, 
In the first move we will delete ‘n’ and put it at the end, ‘S’ = “omn”.
In the second move we will delete ‘o’ from the beginning and put it at the end, ‘S’ = “mno”.
Sample Input 2:
2
1 1      
t
12 12
codingninjas
Sample Output 2:
t
acdgiijnnnos
Hint

Can we obtain all the possible permutations?

Approaches (1)
Sorting

For the value of the ‘K’ > 1 it is possible to obtain any permutation of the string ‘S’. Considering two characters at index ‘i’ and ‘i + 1’ we will prove that it is possible to swap them. 

 

  • We will delete ‘i - 1’ characters from the prefix and put them at the end of the string ‘S’.
  • Now ‘ith’ and ‘i + 1’   characters will be first and second characters now.
  • Now, we will delete the second character and put it at the end of the string ‘S’.
  • Now we will delete the first character and put it at the end of the string ‘S’.

  

After this operation, two characters are swapped.

This way by swapping any two consecutive characters we can obtain any permutation. 

 

For ‘K’ = 1, after any number of operations, we will get one of its circular rotations. 

Eg for “abcd” : “abcd”,  “bcda”, “cdab”, “dabc” are possible.

 

We will compare all the circular rotations and pick the smallest of all as our answer. 

 

The steps are as follows:

 

  1. Create a string named ‘res’ to store the final result and it is initialized to ‘~’.
  2. If ‘K’ > 1:
    1. ‘res’ = all the characters of ‘S’ in sorted order.
  3. Else
    1. To get all the circular permutations we will append one copy of ‘S’ at the end of it and take all the substrings of ‘S’ of length ‘N’.
    2. Iterate from 0 to ‘N’ - 1. (say, iterator = 'i'):
      1. ‘res’ = min(‘res’,  substring(‘S’, i, ’N’ ))
  4. Return ‘res’
Time Complexity

O(N ^ 2), where ‘N’ is the length of the string ‘S’.

 

When ‘K’ = 1, we will compare ‘N’ strings of length ‘N’ to get the lowest possible string. So the overall time complexity will be O(N ^ 2).

Space Complexity

O(N), where ‘N’the length of the string ‘S’.

 

The space required to store the final result ‘res’ will be O (N). So the overall space complexity will be O(N)

Code Solution
(100% EXP penalty)
Smallest String After Ordered Operations
Full screen
Console