Order characters

You are given a string $s (containing only alphabetic characters) and an integer $k > 0. Write a script to choose one of the first $k letters of given string and append it at the end of the string. You keep doing this until you have lexicographically smallest string and return the string.

Examples

Example 1
Input: $str = 'dbca', $k = 1
Output: 'adbc'
Move 1: 'bcad'
Move 2: 'cadb'
Move 3: 'adbc'

Example 2
Input: $str = 'geeks', $k = 2
Output: 'eegks'
First 2 letters: 'g', 'e'
Move 1: 'gekse' (move second letter 'e')
Move 2: 'gksee' (move second letter 'e')
Move 3: 'kseeg'
Move 4: 'seegk'
Move 5: 'eegks'

Example 3
Input: $str = 'cbaed', $k = 3
Output: 'abcde'
First 3 letters: 'c', 'b', 'a'
Move 1: 'cbeda'  (move 'a')
Move 2: 'cedab'  (move 'b')
Move 3: 'edabc'  (move 'c')
Move 4: 'eabcd'  (move 'd')
Move 5: 'abcde'  (move 'e')

Example 4
Input: $str = 'fedcba', $k = 4
Output: 'abcdef'
First 4 letters: 'f', 'e', 'd', 'c'
Move 1: 'fdcbae' (move 'e')
Move 2: 'dcbaef' (move 'f')
Move 3: 'dcbefa' (move 'a')
Move 4: 'dcefab' (move 'b')
Move 5: 'defabc' (move 'c')
Move 6: 'efabcd' (move 'd')
Move 7: 'fabcde' (move 'e')
Move 8: 'abcdef' (move 'f')

Example 5
Input: $str = 'perl', $k = 1
Output: 'erlp'
Move 1: 'erlp' (move 'p')

Example 6
Input: $str = 'oloolooo', $k = 1
Output: 'looloooo'

Example 7
Input: $str = 'oloooolo', $k = 1
Output: 'looloooo'

Analysis

This is a very interesting challenge, and I don't have an entirely satisfactory answer.

Let's set aside $k == 1 for now.

I believe, have tested extensively, but not proved, that for any $s and any $k >= 2 the answer is simply the alphabetically sorted letters which comprise $s.

The challenge does not require us to demostrate or prove this, and we don't have to show the sequence of moves required to get there. I submit therefore that a valid solution is:

join('', sort { $a cmp $b } split(//, $s))

which is simply the concatenation of the sorted letters of $s.

However, I felt it necessary at least to test my theory, so I have submitted a solution where the permitted letter moves are applied randomly until the string matches the sorted string. That isn't very efficient: you'll see from my worked solution that transforming 'equilibrium' to 'beiiilmqruu' took 1713153 letter swaps.

I felt I had to stop somewhere, so limited the process to 10⁷ moves and returned 'failed', because web servers and clients generally impose a time limit. But I have not found any case where it didn't get there eventually, and for shorter words it does so in milliseconds.

It might of course be possible to achieve this in a less random way by considering which move is taking the string nearest to the fully-sorted version, but I tried a few possible strategies and they either didn't work or got into a loop.

Exceptionally, if $k == 1 then all you can do is rotate the letters of $s, and it's easy to find the best answer, which won't necessarily be the sorted version of $s.

Try it 

Your input:

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2026-09-07
use utf8;     # Week 390 - task 2 - Order characters
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

order_characters('dbca', 1);
order_characters('geeks', 2);
order_characters('cbaed', 3);
order_characters('fedcba', 4);
order_characters('perl', 1);
order_characters('oloolooo',1);
order_characters('oloooolo', 1);
order_characters('penguin', 2);
order_characters('moratorium', 4);
order_characters('equilibrium', 6);

sub order_characters {
    
    my ($string, $k, $new, $best, $r, $j, $least, $c, $limit);
    
    ($string, $k) = @_;
    say qq[\nInput:  \$string = '$string', \$k = $k];
    
    # at least two letters
    if ($k >= 2) {
        
        # best = letters fully sorted
        $best = join('', sort { $a cmp $b } split(//, $string));
        
        # randomly select one of the $k initial letters
        $limit = 10 ** 7;
        for ($j = 0; $j <= $limit; $j ++) {
            $r = int(rand($k));         
            $new = '';
            $new .= substr($string, 0, $r) unless $r == 0;
            $new .= substr($string, $r + 1, 99) .=
                    substr($string, $r, 1); 
            last if $new eq $best or $j == $limit;
            $string = $new;
        }

        say qq[Output: ] . ($j <= $limit ? qq[$new ($j tries)] : 
            'failed!');
        
    # only one letter - can only rotate letters
    } elsif ($k == 1) {     
        $best = $string;
        for $k (0 .. length($string) - 1) {
            $string = substr($string, 1, 9999) . 
                      substr($string, 0, 1);
            $best = $string if $string lt $best;
        }
        say qq[Output: '$best'];
    }
}

24 lines of code

Output from script

Input:  $string = 'dbca', $k = 1
Output: 'adbc'

Input:  $string = 'geeks', $k = 2
Output: eegks (42 tries)

Input:  $string = 'cbaed', $k = 3
Output: abcde (34 tries)

Input:  $string = 'fedcba', $k = 4
Output: abcdef (579 tries)

Input:  $string = 'perl', $k = 1
Output: 'erlp'

Input:  $string = 'oloolooo', $k = 1
Output: 'looloooo'

Input:  $string = 'oloooolo', $k = 1
Output: 'looloooo'

Input:  $string = 'penguin', $k = 2
Output: eginnpu (1050 tries)

Input:  $string = 'moratorium', $k = 4
Output: aimmoorrtu (170989 tries)

Input:  $string = 'equilibrium', $k = 5
Output: beiiilmqruu (1713153 tries)