Minimized Rotation String — Problem Statement & Solution Guide
Problem Description
Given a non-empty string source and an integer rotations, find the lexicographically smallest string that can be obtained by performing rotations number of rotations on the source string. A single rotation involves moving the last character of the string to the front.
Examples
Input
source = 'abcdef', rotations = 1
Output
efabcd
Explanation: To find the lexicographically smallest string after rotations, we first perform the given number of rotations on the source string. In this case, we rotate 'abcdef' once, resulting in 'efabcd'.
Input
source = 'aaa', rotations = 1
Output
aaa
Explanation: Since 'aaa' is already the lexicographically smallest string, we return 'aaa' as the result. Note that it's already smallest, not that it's the same after rotation.
Constraints
- 1 ≤ length of string ≤ 10^5
- 1 ≤ k ≤ 10^6
- String contains only lowercase English letters
Optimal Approach & Strategy
The optimized approach involves concatenating the input string with itself and finding the smallest substring of the same length as the input string, resulting in a time complexity of O(n).
Brute Force Approach
The brute-force approach involves rotating the string k times, which results in a time complexity of O(n*k) where n is the length of the string.
Verified Code Solutions
class Solution {
public String minimizedRotationString(String source, int rotations) {
rotations = rotations % source.length();
return source.substring(rotations) + source.substring(0, rotations);
}
}def minimizedRotationString(source: str, rotations: int) -> str:
rotations = rotations % len(source)
return source[rotations:] + source[:rotations]Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.