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.

The contribution of Peter in Week 390 presents a creative stack-based technique which brings the conventional regex-replacement process for string decoding to a new level. The method uses a stack to keep track of the active multiplication factors and thus it demonstrates efficient state management.

This review may cover either or both challenges for this week.

Try it 

Your input:

$string =

eg: solution (max 10 chars)

$k =

eg: 3

⤡

#!/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)