Orderly Queue - Practice Coding Problems

Orderly Queue - Problem

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.

Input & Output

Example 1 — k=1 Rotations Only

$ Input: s = "cba", k = 1

› Output: "acb"

💡 Note: With k=1, we can only move the first character to the end. Possible rotations: "cba" → "bac" → "acb" → "cba". The lexicographically smallest is "acb".

Example 2 — k≥2 Any Permutation

$ Input: s = "cba", k = 2

› Output: "abc"

💡 Note: With k≥2, we can achieve any permutation. The lexicographically smallest permutation is the sorted string "abc".

Example 3 — Already Sorted

$ Input: s = "abc", k = 3

› Output: "abc"

💡 Note: The string is already in lexicographically smallest order, so no changes are needed.

Constraints

1 ≤ s.length ≤ 1000
1 ≤ k ≤ s.length
s consists of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

String s and integer k representing how many front characters we can move

Process

Apply moves optimally based on k value

Output

Lexicographically smallest achievable string

Key Takeaway

🎯 Key Insight: When k≥2, any permutation is achievable, so we can simply sort the string

Asked in

G Google 25 f Facebook 18 a Amazon 15

The key insight is recognizing that when k≥2, we can achieve any permutation of the string, while k=1 only allows rotations. Best approach uses mathematical reasoning: sort the string for k≥2, find best rotation for k=1. Time: O(n²), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Sequences	O(n! × n)	O(n! × n)	Generate all possible sequences of moves and find the lexicographically smallest result
Mathematical Insight	O(n²)	O(n)	Use mathematical properties: k=1 allows only rotations, k≥2 allows any permutation

Brute Force - Try All Sequences — Algorithm Steps

Step 1: Use BFS/DFS to explore all possible move sequences
Step 2: For each state, try moving each of the first k characters to the end
Step 3: Track the lexicographically smallest string encountered

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

Start with original string

Try All Moves

For each state, try moving first k characters to end

Track Best

Keep the lexicographically smallest string found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void rotateString(char* s, char* result, int n) {
    strcpy(result, s + 1);
    result[n-1] = s[0];
    result[n] = '\0';
}

int compare(const void* a, const void* b) {
    return *(char*)a - *(char*)b;
}

char* solution(char* s, int k) {
    int n = strlen(s);
    char* result = malloc((n + 1) * sizeof(char));
    
    if (k == 1) {
        // Only rotations possible
        strcpy(result, s);
        char* current = malloc((n + 1) * sizeof(char));
        strcpy(current, s);
        
        for (int i = 0; i < n; i++) {
            rotateString(current, current, n);
            if (strcmp(current, result) < 0) {
                strcpy(result, current);
            }
        }
        free(current);
        return result;
    } else if (k >= 2) {
        // Any permutation possible, so sort
        strcpy(result, s);
        qsort(result, n, sizeof(char), compare);
        return result;
    }
    
    // For simplicity, use the k>=2 case for general brute force
    strcpy(result, s);
    qsort(result, n, sizeof(char), compare);
    return result;
}

int main() {
    char s[1001];
    int k;
    
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    scanf("%d", &k);
    
    char* result = solution(s, k);
    printf("%s\n", result);
    free(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n! × n)

In worst case, we explore factorial possible states, each taking O(n) to process

⚠ Quadratic Growth

Space Complexity

O(n! × n)

Need to store all possible string states in queue/visited set

⚠ Quadratic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Sequences — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler