Last Updated: 18 Apr, 2021
Smallest String After Ordered Operations
Easy
Asked in company
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]’.
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
Approaches
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:
- Create a string named ‘res’ to store the final result and it is initialized to ‘~’.
- If ‘K’ > 1:
- ‘res’ = all the characters of ‘S’ in sorted order.
- Else
- 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’.
- Iterate from 0 to ‘N’ - 1. (say, iterator = 'i'):
- ‘res’ = min(‘res’, substring(‘S’, i, ’N’ ))
- Return ‘res’