Daily bit(e) of C++ | Lexicographically minimum string
Daily bit(e) of C++ #98, Common interview problem: Lexicographically minimum string
Today we will look at a common C++ interview problem: Lexicographically minimum string.
Given a string and an integer k, you can repeatedly apply the following operation:
take one of the first k characters and append it to the end of the string
Return the lexicographically smallest string you can create this way.
For example, for the string “acbb” and k at least 2, we can, in one operation, move the “c” to the end of the string, creating an optimal “abbc” string.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/9h7nMT7Tq.
Solution
This problem is very much all about the analysis.
Let’s first consider what operation we are doing for k==1. We are moving the first character to the end of the string. This means that we are simply rotating the string, and the lexicographically smallest string is the smallest rotation.
What if we are working with k>=2? We can effectively swap the leading two elements by picking the second element first. Since we can still rotate, we have all the operations we need for producing a lexicographically sorted string.
Putting this together, for k==1, we return the minimum rotation in O(n^2) (note that there are sophisticated algorithms with O(n) complexity), and for k>=2, we return a sorted string in O(n*logn).
