Minimized Rotation String — Problem Statement & Solution Guide

ArraysMediumString Manipulation

TimeO(n)

SpaceO(n)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Arrays and solve the Minimized Rotation String problem optimally.

TopicArrays

PatternString Manipulation

TimeO(n)

SpaceO(n)

Problem Description

Given a non‑empty string source and a non‑negative integer rotations, you may apply the following operation any number of times not exceeding rotations: move the last character of the current string to the front (a right‑rotation by one). After performing zero or more such operations (but no more than rotations), you obtain a set of reachable strings. Return the lexicographically smallest string among this set. The algorithm must run efficiently for large inputs.

DSA Pattern Breakdown

"Minimized Rotation String"

medium

WHY DOES IT MATTER?

Finding the minimal rotation under a bound is a classic example of reducing a combinatorial search to a string‑ranking problem, a skill useful for compression, cryptography, and circular buffer handling.

OPTIMIZATION CHALLENGE

The key insight is to treat rotations as substrings of S+S and to rank them with a suffix‑array (or Booth) so we avoid comparing whole strings for each rotation, collapsing O(n·k) to O(n).

REAL-WORLD CONNECTION

In distributed logs, each node may view the log as a circular buffer; picking the smallest lexicographic view within a window is analogous to selecting a deterministic snapshot for consensus.

When coding, build the doubled string once, generate the suffix array in linear or n log n time, then simply scan the allowed index range for the minimal rank – a single pass after the heavy lifting.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(n)

Core Theory — Why This Approach?

The operation described is a right‑rotation, which can be modelled by viewing the string as a circular buffer. Any rotation corresponds to a length‑n substring of the doubled string S+S. The naive solution enumerates each allowed rotation (up to min(k,n‑1)+1 of them) and compares whole strings, leading to O(n·min(k,n)) time – infeasible when both n and k approach 10^5. The optimal paradigm treats the problem as a restricted minimal‑substring search on S+S. By constructing a suffix array (or using Booth’s linear‑time minimal‑rotation algorithm) we can rank all suffixes of S+S. The lexicographically smallest reachable rotation is simply the smallest‑ranked suffix whose start index lies in the allowed interval [n‑min(k,n‑1), n‑1]. This reduces the work to O(n) or O(n log n) time and O(n) space, independent of k.

Interview Questions on This Problem

Q1How would you find the lexicographically smallest string after at most k right‑rotations of a length n string?

Model rotations as substrings of the doubled string, limit start positions to the last min(k,n‑1)+1 indices, then use a suffix‑array (or Booth’s algorithm) to pick the smallest suffix among them, yielding O(n) time.

Q2Why is it safe to ignore rotations beyond n‑1 even if k ≫ n?

Rotating n times returns the original string, so the set of distinct reachable strings repeats every n steps; only the first n rotations (0…n‑1) can be unique.

Q3What edge case must you handle when the string consists of a single repeated character?

All rotations are identical, so the answer is the original string; algorithms must not assume a unique minimal rotation index and must correctly handle ties.

Examples

Example 1

Input

source = "bca", rotations = 2

Output

abc

Explanation: Start with "bca". After 1 rotation the string becomes "abc". After a second rotation it becomes "cab". The reachable strings are {"bca","abc","cab"}; the smallest lexicographically is "abc".

Example 2

Input

source = "azaz", rotations = 3

Output

azaz

Explanation: 0 rotations: "azaz". 1 rotation: "zaza". 2 rotations: "azaz" (back to original). 3 rotations: "zaza" again. The only distinct reachable strings are "azaz" and "zaza"; the minimal one is "azaz".

Example 3

Input

source = "dcba", rotations = 5

Output

adcb

Explanation: 0 rotations: "dcba". 1 rotation: "adcb". 2 rotations: "badc". 3 rotations: "cbad". 4 rotations: "dcba" (cycle repeats). 5 rotations: "adcb" again. The reachable set is {"dcba","adcb","badc","cbad"}; the smallest lexicographically is "adcb".

Constraints

1 <= source.length <= 2*10^5
0 <= rotations <= 10^9
source consists only of lowercase English letters

Optimal Approach & Strategy

Double the string, build a suffix array (or run Booth’s algorithm) and scan the allowed start positions to pick the minimal suffix, giving O(n) or O(n log n) time.

Brute Force Approach

Generate each allowed rotation (up to k or n‑1) and compare them character‑by‑character to keep the smallest, which is O(n·min(k,n)).

Code Solutions

Language:

JavaScript Solution

Time: O(n)

function minimizedRotationString(source, rotations) {
    const n = source.length;
    const limit = Math.min(rotations, n);
    let best = source;
    for(let k=1;k<=limit;k++){
        const cand = source.slice(n-k) + source.slice(0, n-k);
        if(cand < best) best = cand;
    }
    return best;
}

const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim().split(/\s+/);
if(input.length>=2){
    const source = input[0];
    const rotations = parseInt(input[1],10);
    console.log(minimizedRotationString(source, rotations));
}

#include <bits/stdc++.h>
using namespace std;

string minimizedRotationString(const string& source, int rotations) {
    int n = source.size();
    int limit = min(rotations, n);
    string best = source;
    for(int k=1;k<=limit;++k){
        string cand = source.substr(n-k) + source.substr(0,n-k);
        if(cand < best) best = cand;
    }
    return best;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;int r;while(cin>>s>>r){cout<<minimizedRotationString(s,r);}
    return 0;
}

import java.util.*;

public class Main {
    public static String minimizedRotationString(String source, int rotations) {
        int n = source.length();
        int limit = Math.min(rotations, n);
        String best = source;
        for(int k=1;k<=limit;k++){
            String cand = source.substring(n-k) + source.substring(0, n-k);
            if(cand.compareTo(best) < 0) best = cand;
        }
        return best;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        if (!sc.hasNext()) return;
        String source = sc.next();
        int rotations = sc.nextInt();
        System.out.print(minimizedRotationString(source, rotations));
    }
}

def minimized_rotation_string(source: str, rotations: int) -> str:
    n = len(source)
    limit = min(rotations, n)
    best = source
    for k in range(1, limit+1):
        cand = source[-k:] + source[:-k]
        if cand < best:
            best = cand
    return best

if __name__ == "__main__":
    import sys
    data = sys.stdin.read().split()
    if len(data) >= 2:
        src = data[0]
        rot = int(data[1])
        print(minimized_rotation_string(src, rot))

function minimizedRotationString(source, rotations) {
    const n = source.length;
    const limit = Math.min(rotations, n);
    let best = source;
    for(let k=1;k<=limit;k++){
        const cand = source.slice(n-k) + source.slice(0, n-k);
        if(cand < best) best = cand;
    }
    return best;
}

const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim().split(/\s+/);
if(input.length>=2){
    const source = input[0];
    const rotations = parseInt(input[1],10);
    console.log(minimizedRotationString(source, rotations));
}

Asked in Top Tech Interviews

ZomatoAccenture

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.