Task — Balance string

You are given a string made up of lowercase English letters and digits only. Write a script to rearrange the characters in the given string such that no letter is followed by another letter and no digit is followed by another digit. If there are multiple valid rearrangements, return the lexicographically smallest one. Return an empty string if it is impossible to format the string in that way.

Examples

Example 1
Input: $str = 'a0b1c2'
Output: '0a1b2c'

Example 2
Input: $str = 'abc12'
Output: 'a1b2c'

Example 3
Input: $str = '0a2b1c3'
Output: '0a1b2c3'

Example 4
Input: $str = '1a23'
Output: ''

Example 5
Input: $str = 'ab123'
Output: '1a2b3'

Analysis

We are given a string of mixed lower case letters and numbers and asked to rearrange the characters such that:

• no letter is immediately followed by a letter,
• no number by a number,
• and no other rearrangement precedes this one lexicographically.

The task will clearly only be possible if the number of letters and the number of numbers are equal or differ by ±1. If they are equal, or if there is one more number than letters, the result string will start with a number, or otherwise - if there is one more letter than numbers - it will start (and end) with a letter.

So my algorithm is:

• sort the input string lexicographically
• split that into an array of numbers and an array of letters
• return an empty string if the number of numbers and the number of letters differ by more than 1
• merge the two arrays like a zip ...
• ... starting the zip with a letter if there are more letters than numbers or else with a number

Note that if there are equal numbers of letters and numbers, the result must start with a number because, for example, 0a1b2c will sort before a0b1c2.

Probably someone will come up with more concise code than I have, but I cannot immediately think of a faster algorithm.

In real life, as always, I would start by testing the validity of the statement that the string comprises 'lowercase English letters and digits only' - does that for example mean 'one or more' or 'zero or more'? My code assumes zero or more of each. I would also seek clarity as to the desired result if the input is an empty string.

Try it 

#!/usr/bin/perl

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

use v5.26;    # The Weekly Challenge - 2025-10-06
use utf8;     # Week 342 - task 1 - Balance string
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

balance_string('a0b1c2');
balance_string('abc12');
balance_string('0a2b1c3');
balance_string('1a23');
balance_string('ab123');
balance_string('theweeklychallenge987654321098765432');
balance_string('');
balance_string('z');
balance_string('9');

sub balance_string {
    
    my (@symbols, @letters, @numbers, $c, $result, $diff, $paired);
    
    # sort string
    @symbols = sort(split('', $_[0]));
    @numbers = @letters = ();
    
    # separate numbers and letters
    for $c (@symbols) {
        if ($c lt 'a') { push(@numbers, $c) }
        else           { push(@letters, $c) }
    }
    
    # create result
    $diff = @letters - @numbers;
    if (abs($diff) <= 1 and @symbols) {
        $paired = $diff < 0 ? @letters : @numbers;
        $result  = shift(@letters) if $diff == 1;
        $result .= shift(@numbers) . shift(@letters) for 1 .. $paired;
        $result .= shift(@numbers) if $diff == -1;
    } else {
        $result = '';
    }
    
    say qq[\nInput:  '$_[0]'];
    say qq[Output: '$result'];
}

Output

Input:  'a0b1c2'
Output: '0a1b2c'

Input:  'abc12'
Output: 'a1b2c'

Input:  '0a2b1c3'
Output: '0a1b2c3'

Input:  '1a23'
Output: ''

Input:  'ab123'
Output: '1a2b3'

Input:  'theweeklychallenge987654321098765432'
Output: '0a1c2e2e3e3e4e4g5h5h6k6l7l7l8n8t9w9y'

Input:  ''
Output: ''

Input:  'z'
Output: 'z'

Input:  '9'
Output: '9'