Lexicographically Smallest String with K-Position Moves

Problem

You are given a string of length N and a parameter k. The string can be manipulated by taking one of the first k letters and moving it to the end.

Write a program to determine the lexicographically smallest string that can be created after an unlimited number of moves.

For example, suppose we are given the string daily and k = 1. The best we can create in this case is ailyd.

Examples

Example 1

Input: s = "daily", k = 1
Output: "ailyd"
Explanation:
With k=1, we can only move the first character to the end.
Starting: "daily"
Move 'd' to end: "ailyd" 
This is the lexicographically smallest we can achieve.

Example 2

Input: s = "dcba", k = 2
Output: "abcd"
Explanation:
With k=2, we can move either the first or second character to the end.
Starting: "dcba"
Move 'd' to end: "cbad"
Move 'c' to end: "badc"
Move 'b' to end: "adcb"
Move 'a' to end: "dcba" (back to start)
But we can also:
Starting: "dcba"
Move 'c' to end: "dbac"
Move 'd' to end: "bacd"
Move 'b' to end: "acdb"
Move 'a' to end: "cdba"
Continue optimally to get: "abcd"

Example 3

Input: s = "abc", k = 3
Output: "abc"
Explanation:
The string is already lexicographically smallest.
No moves needed.

Example 4

Input: s = "cba", k = 1
Output: "acb"
Explanation:
With k=1, we can only move the first character to the end.
Starting: "cba"
Move 'c' to end: "bac"
Move 'b' to end: "acb"
Move 'a' to end: "cba" (cycle back)
The smallest achievable is "acb".

Example 5

Input: s = "edcba", k = 4
Output: "abcde"
Explanation:
With k=4, we can move any of the first 4 characters to the end.
Through optimal moves, we can arrange the string in sorted order: "abcde".

Solution

Method 1 - Simulation with Set to Track States

Intuition

Since we can perform unlimited moves and each move is deterministic (move one of first k characters to end), we can simulate all possible states reachable from the initial string. We use a set to track visited states to avoid infinite loops and find the lexicographically smallest string among all reachable states.

Approach

1. Use a set to store all possible string configurations we can reach
2. Use a queue for BFS to explore all reachable states systematically
3. For each string state, generate all possible next states by moving each of the first k characters to the end
4. Continue until no new states can be generated
5. Return the lexicographically smallest string from all reachable states

Code

C++

class Solution {
public:
    string smallestString(string s, int k) {
        unordered_set<string> visited;
        queue<string> q;
        string ans = s;
        
        q.push(s);
        visited.insert(s);
        
        while (!q.empty()) {
            string curr = q.front();
            q.pop();
            
            if (curr < ans) {
                ans = curr;
            }
            
            // Try moving each of the first k characters to the end
            for (int i = 0; i < min(k, (int)curr.length()); i++) {
                string next = curr.substr(1, i) + curr.substr(i + 1) + curr[i];
                
                if (visited.find(next) == visited.end()) {
                    visited.insert(next);
                    q.push(next);
                }
            }
        }
        
        return ans;
    }
};

Go

func smallestString(s string, k int) string {
    visited := make(map[string]bool)
    queue := []string{s}
    ans := s
    
    visited[s] = true
    
    for len(queue) > 0 {
        curr := queue[0]
        queue = queue[1:]
        
        if curr < ans {
            ans = curr
        }
        
        // Try moving each of the first k characters to the end
        for i := 0; i < min(k, len(curr)); i++ {
            next := curr[1:i+1] + curr[i+1:] + string(curr[i])
            
            if !visited[next] {
                visited[next] = true
                queue = append(queue, next)
            }
        }
    }
    
    return ans
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Java

class Solution {
    public String smallestString(String s, int k) {
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        String ans = s;
        
        queue.offer(s);
        visited.add(s);
        
        while (!queue.isEmpty()) {
            String curr = queue.poll();
            
            if (curr.compareTo(ans) < 0) {
                ans = curr;
            }
            
            // Try moving each of the first k characters to the end
            for (int i = 0; i < Math.min(k, curr.length()); i++) {
                String next = curr.substring(1, i + 1) + curr.substring(i + 1) + curr.charAt(i);
                
                if (!visited.contains(next)) {
                    visited.add(next);
                    queue.offer(next);
                }
            }
        }
        
        return ans;
    }
}

Python

class Solution:
    def smallest_string(self, s: str, k: int) -> str:
        visited = set()
        queue = [s]
        ans = s
        
        visited.add(s)
        
        while queue:
            curr = queue.pop(0)
            
            if curr < ans:
                ans = curr
            
            # Try moving each of the first k characters to the end
            for i in range(min(k, len(curr))):
                next_str = curr[1:i+1] + curr[i+1:] + curr[i]
                
                if next_str not in visited:
                    visited.add(next_str)
                    queue.append(next_str)
        
        return ans

Complexity

• ⏰ Time complexity: O(n! * n), in worst case we might generate all permutations of the string, and each string comparison takes O(n)
• 🧺 Space complexity: O(n! * n), to store all possible string states in the visited set

Method 2 - Optimized Rotation-Based Approach

Intuition

When k >= n, we can move any character to any position, so we can sort the string. When k < n, we're essentially looking for the lexicographically smallest rotation that's reachable by our limited moves. We can optimize by recognizing that we're performing a form of constrained rotation.

Approach

1. If k >= length of string, we can rearrange characters in any order, so return sorted string
2. Otherwise, use a more targeted approach to find the optimal rotation
3. For each possible rotation, check if it's reachable with our k-constraint
4. Track the minimum lexicographical string among reachable rotations
5. Use mathematical insight that with k moves per step, we can reach certain patterns more efficiently

Code

C++

class Solution {
public:
    string smallestStringOptimized(string s, int k) {
        int n = s.length();
        
        // If k >= n, we can arrange characters in any order
        if (k >= n) {
            sort(s.begin(), s.end());
            return s;
        }
        
        string ans = s;
        set<string> reachable;
        
        // Generate all reachable strings using constraint
        function<void(string)> generate = [&](string curr) {
            if (reachable.count(curr)) return;
            reachable.insert(curr);
            
            if (curr < ans) {
                ans = curr;
            }
            
            // Try moving each of first k characters to end
            for (int i = 0; i < min(k, n); i++) {
                string next = curr.substr(1, i) + curr.substr(i + 1) + curr[i];
                if (!reachable.count(next)) {
                    generate(next);
                }
            }
        };
        
        generate(s);
        return ans;
    }
};

Go

func smallestStringOptimized(s string, k int) string {
    n := len(s)
    
    // If k >= n, we can arrange characters in any order
    if k >= n {
        chars := []rune(s)
        sort.Slice(chars, func(i, j int) bool {
            return chars[i] < chars[j]
        })
        return string(chars)
    }
    
    ans := s
    reachable := make(map[string]bool)
    
    var generate func(string)
    generate = func(curr string) {
        if reachable[curr] {
            return
        }
        reachable[curr] = true
        
        if curr < ans {
            ans = curr
        }
        
        // Try moving each of first k characters to end
        for i := 0; i < min(k, n); i++ {
            next := curr[1:i+1] + curr[i+1:] + string(curr[i])
            if !reachable[next] {
                generate(next)
            }
        }
    }
    
    generate(s)
    return ans
}

Java

class Solution {
    private String ans;
    private Set<String> reachable;
    
    public String smallestStringOptimized(String s, int k) {
        int n = s.length();
        
        // If k >= n, we can arrange characters in any order
        if (k >= n) {
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            return new String(chars);
        }
        
        ans = s;
        reachable = new HashSet<>();
        
        generate(s, k, n);
        return ans;
    }
    
    private void generate(String curr, int k, int n) {
        if (reachable.contains(curr)) return;
        reachable.add(curr);
        
        if (curr.compareTo(ans) < 0) {
            ans = curr;
        }
        
        // Try moving each of first k characters to end
        for (int i = 0; i < Math.min(k, n); i++) {
            String next = curr.substring(1, i + 1) + curr.substring(i + 1) + curr.charAt(i);
            if (!reachable.contains(next)) {
                generate(next, k, n);
            }
        }
    }
}

Python

class Solution:
    def smallest_string_optimized(self, s: str, k: int) -> str:
        n = len(s)
        
        # If k >= n, we can arrange characters in any order
        if k >= n:
            return ''.join(sorted(s))
        
        self.ans = s
        reachable = set()
        
        def generate(curr: str) -> None:
            if curr in reachable:
                return
            reachable.add(curr)
            
            if curr < self.ans:
                self.ans = curr
            
            # Try moving each of first k characters to end
            for i in range(min(k, n)):
                next_str = curr[1:i+1] + curr[i+1:] + curr[i]
                if next_str not in reachable:
                    generate(next_str)
        
        generate(s)
        return self.ans

Complexity

• ⏰ Time complexity: O(n!) in worst case, but significantly better average case due to early termination and pruning
• 🧺 Space complexity: O(n!) for storing reachable states, but with better space locality

Method 3 - Mathematical Pattern Recognition

Intuition

For certain values of k and string patterns, we can mathematically determine the optimal result without exhaustive search. When k=1, we're essentially performing rotations. When k is large, we approach full sorting capability. We can identify patterns and shortcuts.

Approach

1. Handle special cases: k=1 (pure rotation), k>=n (full sorting)
2. For k=1, find the lexicographically smallest rotation
3. For k>=n, return sorted string
4. For intermediate k values, use cycle detection and pattern analysis
5. Optimize by recognizing that certain character arrangements are unreachable

Code

C++

class Solution {
public:
    string smallestStringPattern(string s, int k) {
        int n = s.length();
        
        if (k >= n) {
            sort(s.begin(), s.end());
            return s;
        }
        
        if (k == 1) {
            // Find lexicographically smallest rotation
            string doubled = s + s;
            string minRotation = s;
            
            for (int i = 1; i < n; i++) {
                string rotation = doubled.substr(i, n);
                if (rotation < minRotation) {
                    minRotation = rotation;
                }
            }
            return minRotation;
        }
        
        // For general k, use limited BFS with pruning
        set<string> visited;
        priority_queue<string, vector<string>, greater<string>> pq;
        
        pq.push(s);
        visited.insert(s);
        
        while (!pq.empty()) {
            string curr = pq.top();
            pq.pop();
            
            // If we found a very good string, likely optimal
            if (curr <= s) {
                return curr;
            }
            
            for (int i = 0; i < min(k, n); i++) {
                string next = curr.substr(1, i) + curr.substr(i + 1) + curr[i];
                
                if (visited.find(next) == visited.end()) {
                    visited.insert(next);
                    pq.push(next);
                    
                    // Limit search space
                    if (visited.size() > 1000) {
                        goto done;
                    }
                }
            }
        }
        
        done:
        return *visited.begin();
    }
};

Go

func smallestStringPattern(s string, k int) string {
    n := len(s)
    
    if k >= n {
        chars := []rune(s)
        sort.Slice(chars, func(i, j int) bool {
            return chars[i] < chars[j]
        })
        return string(chars)
    }
    
    if k == 1 {
        // Find lexicographically smallest rotation
        doubled := s + s
        minRotation := s
        
        for i := 1; i < n; i++ {
            rotation := doubled[i:i+n]
            if rotation < minRotation {
                minRotation = rotation
            }
        }
        return minRotation
    }
    
    // For general k, use limited search
    visited := make(map[string]bool)
    var candidates []string
    
    var dfs func(string, int)
    dfs = func(curr string, depth int) {
        if depth > 20 || visited[curr] { // Limit depth
            return
        }
        visited[curr] = true
        candidates = append(candidates, curr)
        
        for i := 0; i < min(k, n); i++ {
            next := curr[1:i+1] + curr[i+1:] + string(curr[i])
            if !visited[next] {
                dfs(next, depth+1)
            }
        }
    }
    
    dfs(s, 0)
    
    sort.Strings(candidates)
    return candidates[0]
}

Java

class Solution {
    public String smallestStringPattern(String s, int k) {
        int n = s.length();
        
        if (k >= n) {
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            return new String(chars);
        }
        
        if (k == 1) {
            // Find lexicographically smallest rotation
            String doubled = s + s;
            String minRotation = s;
            
            for (int i = 1; i < n; i++) {
                String rotation = doubled.substring(i, i + n);
                if (rotation.compareTo(minRotation) < 0) {
                    minRotation = rotation;
                }
            }
            return minRotation;
        }
        
        // For general k, use limited search with pruning
        Set<String> visited = new HashSet<>();
        List<String> candidates = new ArrayList<>();
        
        dfs(s, k, n, visited, candidates, 0);
        
        Collections.sort(candidates);
        return candidates.get(0);
    }
    
    private void dfs(String curr, int k, int n, Set<String> visited, List<String> candidates, int depth) {
        if (depth > 20 || visited.contains(curr)) { // Limit depth
            return;
        }
        visited.add(curr);
        candidates.add(curr);
        
        for (int i = 0; i < Math.min(k, n); i++) {
            String next = curr.substring(1, i + 1) + curr.substring(i + 1) + curr.charAt(i);
            if (!visited.contains(next)) {
                dfs(next, k, n, visited, candidates, depth + 1);
            }
        }
    }
}

Python

class Solution:
    def smallest_string_pattern(self, s: str, k: int) -> str:
        n = len(s)
        
        if k >= n:
            return ''.join(sorted(s))
        
        if k == 1:
            # Find lexicographically smallest rotation
            doubled = s + s
            min_rotation = s
            
            for i in range(1, n):
                rotation = doubled[i:i+n]
                if rotation < min_rotation:
                    min_rotation = rotation
            return min_rotation
        
        # For general k, use limited search
        visited = set()
        candidates = []
        
        def dfs(curr: str, depth: int) -> None:
            if depth > 20 or curr in visited:  # Limit depth
                return
            visited.add(curr)
            candidates.append(curr)
            
            for i in range(min(k, n)):
                next_str = curr[1:i+1] + curr[i+1:] + curr[i]
                if next_str not in visited:
                    dfs(next_str, depth + 1)
        
        dfs(s, 0)
        return min(candidates)

Complexity

• ⏰ Time complexity: O(n²) for k=1 case, O(n log n) for k>=n case, O(limited search) for general case
• 🧺 Space complexity: O(n) for k=1, O(1) for k>=n, O(limited states) for general case

Notes

• Method 1 provides a complete solution using BFS to explore all reachable states
• Method 2 optimizes by handling special cases (k>=n means full sorting capability)
• Method 3 adds pattern recognition for common cases like k=1 (pure rotation) and uses depth-limited search for complex cases
• The problem has interesting mathematical properties related to string rotations and permutation reachability
• When k=1, the problem reduces to finding the lexicographically smallest rotation of the string
• When k>=n, we can achieve any permutation, so the answer is simply the sorted string
• For intermediate k values, the reachable configurations form a complex but finite state space
• The time complexity can be exponential in worst case, but practical inputs often have much better performance
• Consider using memoization or dynamic programming for very large inputs with repeated subproblems