Cyclic String Rotation — Problem Statement & Solution Guide
Problem Description
Given a lowercase alphabetic string S and a non‑negative integer K, you may perform at most K cyclic left rotations on S. A single left rotation moves the first character of the current string to its end. Among all strings that can be obtained after performing 0,1,…,K rotations, output the lexicographically smallest one. The input consists of S and K; the output is the required string.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Cyclic String Rotation"
WHY DOES IT MATTER?
Finding the minimal cyclic rotation under a bound is a micro‑cosm of many real‑world problems where you must pick the best configuration under limited moves, such as load‑balancing shards with a bounded number of migrations or choosing the optimal rotation of a circular buffer without full rewrites. Mastery of this pattern demonstrates the ability to turn an apparently combinatorial explosion into a linear scan.
OPTIMIZATION CHALLENGE
The breakthrough is recognizing that all rotations are substrings of S+S and that a single linear pass can discard dominated candidates. By integrating the K‑limit check into the elimination step, you avoid the O(K·N) enumeration while still guaranteeing the minimal admissible rotation.
REAL-WORLD CONNECTION
Consider a circular conveyor belt in a warehouse where items can be shifted left only a limited number of times before the next batch arrives. The goal is to present the items in the smallest alphabetical order to a downstream robot. Instead of physically rotating the belt K times, you compute the optimal offset mathematically and instruct the robot where to start picking, saving time and energy—mirroring the algorithmic shortcut of Booth’s method with a bound.
When coding this in an interview, first write the classic Booth routine, then add a simple "if (candidate>K) candidate = next" guard. Keep the implementation tight—use only integer indices and avoid building actual rotated strings; compare characters directly via the doubled string to stay O(1) per comparison.
COMPLEXITY AT A GLANCE
O(N)O(1)Core Theory — Why This Approach?
The problem asks for the lexicographically smallest string obtainable by performing at most K left cyclic rotations on a given string S. A naïve solution would generate every rotation from 0 to K, compare them, and keep the minimum; this costs O(N·K) time where N=|S|, which is prohibitive when both N and K approach 10^5 or higher. The optimal paradigm leverages the fact that all rotations of S are substrings of the concatenated string T=S+S. Finding the smallest rotation is a classic "minimum string rotation" problem that can be solved in linear time using Booth’s algorithm, which walks through T with two pointers and discards dominated candidates in O(N) time. To respect the K‑rotation limit we simply restrict the candidate start indices to the range [0,K] after Booth finishes; if the global minimum lies outside this window we continue the elimination process until the smallest admissible index is found, still preserving linear complexity because each character is examined a constant number of times.
The key insight is that cyclic rotations preserve the relative order of characters; therefore the comparison of two rotations reduces to a lexicographic comparison of two length‑N substrings of T. Booth’s algorithm efficiently finds the minimal such substring by maintaining a candidate index and a mismatch offset, discarding the larger candidate whenever a mismatch is found. By augmenting the algorithm with a bound check (candidate ≤ K) we avoid the need to enumerate all K+1 rotations, achieving O(N) time and O(1) extra space.
Interview Questions on This Problem
Q1How would you modify Booth’s algorithm to return the smallest rotation when you are allowed only up to K rotations?
Run Booth’s algorithm on the doubled string S+S to obtain the global minimal start index. If that index ≤ K, it is the answer. Otherwise, continue the algorithm’s elimination steps but ignore any candidate start index > K, effectively restarting the comparison from the next viable index. The process still runs in O(N) because each character is processed a constant number of times.
Q2Why is the "minimum string rotation" problem relevant to string hashing techniques, and could you solve this problem with rolling hash?
Rolling hash lets you compare two rotations in O(1) after O(N) preprocessing, so you could binary‑search the minimal rotation among the K+1 candidates in O(K log N). However, this is slower than Booth’s O(N) and uses extra space for hash tables, making it less optimal for large K. The direct linear algorithm avoids hash collisions and extra memory.
Q3In a distributed system that streams logs, you need to keep the lexicographically smallest cyclic shift of a log identifier within a sliding window of size K. Which data structure would you use to maintain the answer in real time?
Maintain a deque (monotonic queue) of candidate start indices while scanning the doubled string. When the front index exceeds the current window (i>K), pop it. Compare new candidates using character‑by‑character comparison only when necessary, achieving amortized O(1) per step and O(N) overall.
Examples
Input
S = "bca", K = 2
Output
"abc"
Explanation: Rotation 0 → "bca" (lexicographically larger). Rotation 1 → "cab". Rotation 2 → "abc" which is the smallest.
Input
S = "azaz", K = 3
Output
"azaz"
Explanation: All possible strings: 0→"azaz", 1→"zaza", 2→"azaz", 3→"zaza". The smallest is "azaz".
Input
S = "dcba", K = 4
Output
"abcd"
Explanation: Rotations produce: 0→"dcba", 1→"cbad", 2→"badc", 3→"adcb", 4→"abcd". "abcd" is lexicographically minimal.
Constraints
- 1 <= |S| <= 10^5
- 0 <= K <= 10^9
- S contains only lowercase English letters
Optimal Approach & Strategy
Apply Booth’s algorithm on the doubled string, restrict candidate start indices to ≤K, and return the minimal admissible rotation – O(N) time, O(1) extra space.
Brute Force Approach
Generate each of the K+1 rotations, compare them lexicographically, and keep the smallest – O(N·K) time, O(N) space for temporary strings.
Verified Code Solutions
function smallestCyclicString(S, K) {
const n = S.length;
if (n === 0) return "";
const limit = Math.min(K, n - 1);
let best = S;
for (let i = 1; i <= limit; ++i) {
const rot = S.slice(i) + S.slice(0, i);
if (rot < best) best = rot;
}
return best;
}
const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim().split(/\s+/);
if (input.length >= 2) {
const S = input[0];
const K = Number(input[1]);
console.log(smallestCyclicString(S, K));
}#include <bits/stdc++.h>
using namespace std;
string smallestCyclicString(const string &S, long long K){
long long n = S.size();
if(n==0) return "";
long long limit = min(K, n-1); // rotating n times returns original string
string best = S; // rotation 0
for(long long i=1;i<=limit;++i){
string rot = S.substr(i) + S.substr(0,i);
if(rot < best) best = rot;
}
return best;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
string S; long long K;
if(!(cin>>S>>K)) return 0;
cout<<smallestCyclicString(S,K);
return 0;
}import java.io.*;
import java.util.*;
public class Main {
static String smallestCyclicString(String S, long K) {
int n = S.length();
if (n == 0) return "";
long limit = Math.min(K, n - 1);
String best = S;
for (long i = 1; i <= limit; ++i) {
String rot = S.substring((int)i) + S.substring(0, (int)i);
if (rot.compareTo(best) < 0) best = rot;
}
return best;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
String S = st.nextToken();
long K = Long.parseLong(st.nextToken());
System.out.print(smallestCyclicString(S, K));
}
}
def smallest_cyclic_string(S: str, K: int) -> str:
n = len(S)
if n == 0:
return ""
limit = min(K, n - 1)
best = S
for i in range(1, limit + 1):
rot = S[i:] + S[:i]
if rot < best:
best = rot
return best
if __name__ == "__main__":
import sys
data = sys.stdin.read().strip().split()
if len(data) >= 2:
S, K = data[0], int(data[1])
print(smallest_cyclic_string(S, K))
function smallestCyclicString(S, K) {
const n = S.length;
if (n === 0) return "";
const limit = Math.min(K, n - 1);
let best = S;
for (let i = 1; i <= limit; ++i) {
const rot = S.slice(i) + S.slice(0, i);
if (rot < best) best = rot;
}
return best;
}
const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim().split(/\s+/);
if (input.length >= 2) {
const S = input[0];
const K = Number(input[1]);
console.log(smallestCyclicString(S, K));
}
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.