Given a number K, Find the shortest and smallest string which has K positions in it, such that the character at that position is alphabetically greater than the character immediately after it. Only the lower case alphabets [a-z] are allowed.
For example consider K = 1
“ba” is the shortest and smallest string possible. There are other possibilities like “ca”, “bad”. But “ca” cannot be the answer because “ba” is alphabetically smaller than “ca”. Similarly “bad” cannot be the answer because it’s length is greater than “ba”.
This problem is from Codechef. If you want to solve it, follow the problem link.
Here is how we can solve the problem. Let us look at some of the answers.
K = 1, “ba”
K = 2, “cba”
K = 3, “dcba”…
If you observe the pattern, this is simply reverse order of alphabets. We can happily reverse the alphabets if K < 26. What happens if K = 26? The pattern repeats, and the repeating pattern should be added in the beginning.
So for K = 26, the answer is “bazyxwvutsrqponmlkjihgfedcba”.
Here is the Python implementation of this algorithm.