Perl Weekly Challenge 342 - Balance String and Max Score

Task 1: Balance String

"Letters and Digits: Alternate or Bust!"

Given a string of lowercase letters and digits, rearrange it so no letter follows another letter and no digit follows another digit. Return the lexicographically smallest such arrangement, or an empty string if impossible.

The Strategy: Separate and sort letters and digits. If the counts differ by more than 1, no valid arrangement exists. Otherwise, interleave starting with whichever type is more numerous. When counts are equal, start with digits for the smallest lexicographic result.

Perl Implementation

sub balance_string {
    my ($str) = @_;
    my @letters = sort grep /[a-z]/, split //, $str;
    my @digits  = sort grep /\d/,    split //, $str;

    my $diff = @letters - @digits;
    return "" if $diff > 1 || $diff < -1;

    my @result;
    my ( $i, $j ) = ( 0, 0 );

    if ( @letters > @digits ) {
        while ( $i < @letters || $j < @digits ) {
            push @result, $letters[$i] if $i < @letters;
            $i++;
            push @result, $digits[$j] if $j < @digits;
            $j++;
        }
    } else {
        while ( $i < @letters || $j < @digits ) {
            push @result, $digits[$j] if $j < @digits;
            $j++;
            push @result, $letters[$i] if $i < @letters;
            $i++;
        }
    }

    return join "", @result;
}

Python Implementation

def balance_string(text: str) -> str:
    """Rearrange so letters and digits alternate. Lex smallest or empty."""
    letters = sorted(ch for ch in text if ch.isalpha())
    digits = sorted(ch for ch in text if ch.isdigit())

    if abs(len(letters) - len(digits)) > 1:
        return ""

    result = []
    i = j = 0

    if len(letters) > len(digits):
        while i < len(letters) or j < len(digits):
            if i < len(letters):
                result.append(letters[i]); i += 1
            if j < len(digits):
                result.append(digits[j]); j += 1
    else:
        while i < len(letters) or j < len(digits):
            if j < len(digits):
                result.append(digits[j]); j += 1
            if i < len(letters):
                result.append(letters[i]); i += 1

    return "".join(result)

Task 2: Max Score

"Split the Binary: Maximise the Left Zeros + Right Ones!"

Given a binary string, find the maximum score after splitting it into two non-empty parts. The score is the number of zeros in the left part plus the number of ones in the right part.

The Strategy: Try every possible split point from left to right. For each split, count zeros in the left substring and ones in the right substring. Track and return the maximum score across all splits.

Perl Implementation

sub max_score {
    my ($str) = @_;
    return 0 if length $str < 2;

    my $max_score = 0;

    for my $i ( 1 .. length($str) - 1 ) {
        my $left  = substr( $str, 0, $i );
        my $right = substr( $str, $i );

        my $zeros_left = () = $left =~ /0/g;
        my $ones_right = () = $right =~ /1/g;

        my $score = $zeros_left + $ones_right;
        $max_score = $score if $score > $max_score;
    }

    return $max_score;
}

Python Implementation

def max_score(text: str) -> int:
    """Max score after splitting: zeros in left + ones in right."""
    if len(text) < 2:
        return 0

    best = 0
    for i in range(1, len(text)):
        left = text[:i]
        right = text[i:]
        score = left.count("0") + right.count("1")
        best = max(best, score)
    return best