Perl Weekly Challenge 350 - Good Substrings and Shuffle Pairs

Task 1: Good Substrings

"No Repeats: Spotting Clean Triples in a String!"

This week's first task asks us to count how many substrings of length three in a given string have no repeated characters. A substring is "good" when all three characters are unique.

The Strategy: Slide a window of three characters across the string from left to right. For each window, check whether all three characters are distinct by converting the substring to a set and verifying it has exactly three elements. Increment the counter for each good substring found.

Perl Implementation

sub good_substrings ($str) {
    ($str) = $STR_CHECK->($str);
    my $n = length $str;
    return 0 if $n < 3;

    my $count = 0;
    for my $i ( 0 .. $n - 3 ) {
        my $sub = substr( $str, $i, 3 );
        my %seen;
        $seen{$_}++ for split //, $sub;
        ++$count if keys(%seen) == 3;
    }
    return $count;
}

Python Implementation

def good_substrings(text: str) -> int:
    """Return the number of length-3 substrings with all distinct characters."""
    if len(text) < 3:
        return 0

    count = 0
    for idx in range(len(text) - 2):
        chunk = text[idx : idx + 3]
        if len(set(chunk)) == 3:
            count += 1
    return count

Task 2: Shuffle Pairs

"Mixed Digits, Same Value: Finding the Hidden Multipliers!"

The second task defines a shuffle pair as two integers A and B that contain the same digits in a different order, where B = A * k for some integer k (the "witness"). Given a range and a count, we need to find how many integers in that range participate in at least the requested number of shuffle pairs.

The Strategy: For each number in the range, sort its digits to create a "signature". Then iterate over all relevant multipliers k >= 2 and check whether the product falls within the same digit-length range and has the same digit signature. Track the number of distinct witnesses for each integer. Finally, count how many integers meet or exceed the required witness count.

Perl Implementation

sub _signature ($n) {
    return join '', sort split //, "$n";
}

sub shuffle_pairs_count ($from, $to, $count) {
    ( $from, $to, $count ) = $INT_CHECK->( $from, $to, $count );
    die 'Expected $from <= $to' if $from > $to;
    die 'Expected $count >= 1' if $count < 1;

    my %witnesses;

    for my $a ( $from .. $to ) {
        my $sig_a = _signature($a);
        my $digits = length $a;
        my $max    = 10**$digits - 1;
        my $kmax   = int( $max / $a );
        next if $kmax < 2;

        for my $k ( 2 .. $kmax ) {
            my $b = $a * $k;
            next if length($b) != length($a);
            next if _signature($b) ne $sig_a;
            $witnesses{$a}{$k} = 1;
        }
    }

    my $qualified = 0;
    for my $a ( $from .. $to ) {
        my $num = $witnesses{$a} ? scalar keys %{ $witnesses{$a} } : 0;
        ++$qualified if $num >= $count;
    }
    return $qualified;
}

Python Implementation

def _signature(n: int) -> str:
    return ''.join(sorted(str(n)))


def shuffle_pairs_count(from_val: int, to_val: int, count: int) -> int:
    """
    Returns the number of integers in [from_val, to_val] that belong to
    at least `count` different shuffle pairs.
    """
    if from_val > to_val:
        raise ValueError("Expected from <= to")
    if count < 1:
        raise ValueError("Expected count >= 1")

    witnesses: dict[int, set[int]] = {}

    for a in range(from_val, to_val + 1):
        sig_a = _signature(a)
        digits = len(str(a))
        max_val = 10**digits - 1
        kmax = max_val // a
        if kmax < 2:
            continue

        for k in range(2, kmax + 1):
            b = a * k
            if len(str(b)) != digits:
                break
            if _signature(b) != sig_a:
                witnesses.setdefault(a, set()).add(k)

    qualified = 0
    for a in range(from_val, to_val + 1):
        if len(witnesses.get(a, set())) >= count:
            qualified += 1
    return qualified