The Weekly Challenge 265

33% Appearance & Completing Word: Frequency Threshold Analysis and Character Subsets in Perl & Python

Lubos Kolouch April 15, 2024 Challenge Details GitHub Solutions

Task 1: 33% Appearance

You are given an array of integers, @ints.

Write a script to find an integer that appears 33% or more of the time in the given array.

If there is more than one such integer, return the smallest one. If no such integer exists, return undef / None.

Example 1: Input: @ints = (1, 2, 3, 3, 3, 3, 4, 2) → Output: 3

Example 2: Input: @ints = (1, 1) → Output: 1

Example 3: Input: @ints = (1, 2, 3) → Output: 1

Method Explanation

The problem requires identifying any integer whose appearance rate in an array meets or exceeds 33% (i.e. $\text{count} / n \ge 0.33$). In case multiple numbers satisfy this criterion, we must choose the smallest integer.

Our approach is straightforward:

  1. If the array is empty, return undef (or None).
  2. Compute frequency counts for every number using a hash table in Perl or a Counter in Python.
  3. Filter the candidates whose relative frequency meets or exceeds 33% ($\ge 0.33$).
  4. If any candidates qualify, return the minimum integer; otherwise return undef / None.

This approach runs in $O(N)$ time to count occurrences, followed by sorting or finding the minimum among at most three candidates (since at most 3 distinct numbers can each appear ≥ 33% of the time). Memory usage is $O(U)$ where $U$ is the number of distinct integers in the array.

Perl Solution

use v5.38;
use warnings;
use Type::Params -sigs;
use Types::Standard qw(ArrayRef Int);

signature_for find_integer_appearing_33_percent_or_more => (
    method     => 0,
    positional => [ ArrayRef [Int] ],
);

sub find_integer_appearing_33_percent_or_more ($ints) {
    return unless @$ints;

    my $n = scalar @$ints;
    my %count;
    $count{$_}++ for @$ints;

    my @valid_numbers = grep { ( $count{$_} / $n ) >= 0.33 } keys %count;
    return unless @valid_numbers;

    @valid_numbers = sort { $a <=> $b } @valid_numbers;
    return $valid_numbers[0];
}

Python Solution

from collections import Counter


def find_integer_appearing_33_percent_or_more(ints: list[int]) -> int | None:
    """Find an integer that appears 33% or more of the time in the given list."""
    if not ints:
        return None

    counts = Counter(ints)
    n = len(ints)

    valid_numbers = [num for num, cnt in counts.items() if (cnt / n) >= 0.33]

    return min(valid_numbers) if valid_numbers else None

Task 2: Completing Word

You are given a string, $str, and an array of strings, @words.

Write a script to find the shortest completing word in the given array of strings.

A completing word is a word that contains all the letters in the given string (ignoring case and numbers/special characters). If a letter appears more than once in the given string, then it must appear that many times or more in the completing word.

If there are multiple shortest completing words, return the first one that occurs in the array.

Example 1: Input: $str = 'aBc 11c', @words = ('accbbb', 'abc', 'abbc') → Output: 'accbbb'

Example 2: Input: $str = 'Da2 abc', @words = ('abcm', 'baacd', 'abaadc') → Output: 'baacd'

Example 3: Input: $str = 'JB 007', @words = ('jj', 'bb', 'bjb') → Output: 'bjb'

Method Explanation

To determine whether a candidate word is a "completing word", we must ensure that it contains every letter from the target string with a multiplicity at least as high as in the target, while ignoring digits, spaces, and casing.

  1. Extract and lowercase all alphabetic characters from the target string, counting their frequencies into a multi-set (histogram).
  2. For each word in the list, build its lowercase letter frequency table.
  3. A word is valid if for every letter present in the target histogram, the candidate word contains at least that many occurrences of the letter. In Python, this can be succinctly expressed by subtracting Counter objects: not (target_count - word_count).
  4. Among all valid completing words, select the shortest word. In both Perl and Python, ties are broken by taking the word that appears earliest in the candidate list.

This solution inspects each character of the target and candidate words once, running in $O(|S| + \sum |W_i|)$ time and $O(1)$ auxiliary space (bounded by the 26-character English alphabet).

Perl Solution

use v5.38;
use warnings;
use Type::Params -sigs;
use Types::Standard qw(ArrayRef Str);

signature_for shortest_completing_word => (
    method     => 0,
    positional => [ Str, ArrayRef [Str] ],
);

sub _get_letter_counts ($s) {
    my %counts;
    for my $char ( split //, lc $s ) {
        if ( $char =~ /^[a-z]$/ ) {
            $counts{$char}++;
        }
    }
    return \%counts;
}

sub _is_completing ( $target_count, $word ) {
    my $word_count = _get_letter_counts($word);
    for my $letter ( keys %$target_count ) {
        return 0 if ( $word_count->{$letter} // 0 ) < $target_count->{$letter};
    }
    return 1;
}

sub shortest_completing_word ( $target, $words ) {
    my $target_count = _get_letter_counts($target);
    my $shortest;

    for my $word (@$words) {
        if ( _is_completing( $target_count, $word ) ) {
            if ( !defined $shortest || length($word) < length($shortest) ) {
                $shortest = $word;
            }
        }
    }

    return $shortest // '';
}

Python Solution

from collections import Counter


def _get_letter_counts(s: str) -> Counter[str]:
    """Count case-insensitive alphabetic characters in a string."""
    return Counter(c.lower() for c in s if c.isalpha())


def shortest_completing_word(target: str, words: list[str]) -> str:
    """Find the shortest completing word in the given list of words."""
    target_count = _get_letter_counts(target)

    valid_words = [
        word for word in words if not (target_count - _get_letter_counts(word))
    ]
    return min(valid_words, key=len) if valid_words else ""