Problem Description
You are given a string s and an integer k. You can choose one of the first k letters of s and append it at the end of the string. Return the lexicographically smallest string you could have after applying the mentioned step any number of moves.
Key Insights
- If k = 1, we can only move the first character to the end, which allows us to rearrange the string but not completely sort it.
- If k > 1, we can rearrange the string in any order since we can effectively perform any number of moves using the first k characters.
- The lexicographically smallest string can be obtained by sorting the string when k > 1.
Space and Time Complexity
Time Complexity: O(n log n) when k > 1 (for sorting), O(n^2) when k = 1 (for generating all rotations and finding the minimum). Space Complexity: O(n) for storing the sorted string or the rotated strings.
Solution
For k = 1, we can only rearrange the string by moving the first character to the end. We can generate all possible rotations of the string and find the smallest one. For k > 1, we can sort the entire string directly to get the lexicographically smallest result.