PWC 350 Good Substring / Shuffle Pairs

Source: Dev.to

Task 1: Good Substrings

The Task

You are given a string. Write a script to return the number of good substrings of length three in the given string. A substring is good if it contains no repeated characters.

Examples

The Think‑y Part

A regular expression could solve this, but the simplest approach is to slide a window of three characters across the string and check that all three are distinct.

The Code‑y Part

sub goodSubstring($str) {
    my $good = 0;
    my @s = split //, $str;
    for (0 .. $#s - 2) {
        my ($first, $second, $third) = @s[$_, $_+1, $_+2];
        $good++ if $first ne $second && $first ne $third && $second ne $third;
    }
    return $good;
}

Notes

• The string is split into a list of characters for easy indexing.
• An array slice @s[$_, $_+1, $_+2] extracts three consecutive characters.
• Since only three characters are involved, checking pairwise inequality is straightforward.

Task 2: Shuffle Pairs

The Task

For two integers A ≤ B that consist of the same digits in a different order, we call them a shuffle pair if there exists an integer k such that A = B * k. The integer k is the witness of the pair.

Write a function that, given $from, $to, and $count, returns the number of integers i in the range $from ≤ i ≤ $to that belong to at least $count different shuffle pairs.

Examples

1. Input: $from = 1, $to = 1000, $count = 1
   Output: 0 – no shuffle pairs under 1000.

2. Input: $from = 1500, $to = 2500, $count = 1
   Output: 3 – the numbers are 1782 (→ 7128, k=4), 2178 (→ 8712, k=4), 2475 (→ 7425, k=3).

3. Input: $from = 1_000_000, $to = 1_500_000, $count = 5
   Output: 2 – 1428570 and 1429857, each with five shuffle partners.

4. Input: $from = 13_427_000, $to = 14_100_000, $count = 2
   Output: 11 – six numbers have three partners, five have two.

5. Input: $from = 1030, $to = 1130, $count = 1
   Output: 2 – 1035 (→ 3105, k=3) and 1089 (→ 9801, k=9).

Deliberations

The problem is best tackled by brute force with a few optimizations:

1. Canonical form: Sort the digits of a number; two numbers are permutations of each other iff their canonical forms match.
2. Search space: For a given n, only multiples 2..9 can stay within the same digit length. Multiples beyond that would add a digit and cannot be a shuffle pair.
3. Early bail‑outs:
   • Compute the maximum possible value with the same number of digits (999…).
   • Quickly reject a multiple if its first or last digit does not appear in the original number.

Helper: Canonical Form

sub canonical($n) {
    join "", sort split //, $n;
}

Main Solution

sub shufflePair($from, $to, $count) {
    my $answer = 0;

    for my $n ($from .. $to) {
        my $base = canonical($n);
        my $max  = (9 x length($n)) + 0;   # e.g., 999 for a 3‑digit number
        my $pair = 0;

        for my $k (2 .. 9) {
            my $multiple = $n * $k;
            next if $multiple > $max
                 || index($base, substr($multiple, 0, 1)) = $count;
        }
    }
    return $answer;
}

Notes

• canonical($n) is cached as $base for each n.
• $max limits the search to numbers that could still have the same digit count.
• The cheap digit checks (index on first/last digit) avoid unnecessary sorting.
• The final count increments when a number has at least $count shuffle partners.