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

To start, if $k == 1 then all you can do is rotate the letters of the word, and it's easy to find the best answer.

But, I've been in Germany for the last week visiting a few castles, having complicated conversations in German, and singing a song about a hippopotamus, so my brain is maybe not in top form.

And maybe that's why I found this challenge with $k > 1 quite difficult. I tried a few criteria for deciding which letter to move to the end, and while they all had their sucesses, they also had their failures.

So I have submitted a solution that:

• Works for all of Mohammad's examples
• Works typically for 8 letter words if $k >= 3, and for longer words where $k is larger and shorter ones where $k == 2

It works by simply choosing the letter to move at random - within the range 0 .. $k - 1, and trying up to 10⁷ moves to get to an arrangement where all the letters are in alphabetical order.

This supposes that a permutation where all the letters are in alphabetical order can be reached when the rules of the challenge are applied, and while I can't prove it, I postulate that this is always the case where $k >= 2.

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)