The Weekly Challenge 255

Odd Character & Most Frequent Word

Official Challenge • Solutions on GitHub

Task 1: Odd Character

You are given two strings, $s and $t. The string $t is generated using the shuffled characters of the string $s with an additional character. Write a script to find the additional character in the string $t.

Examples

Example 1: Input: $s = "Perl", $t = "Preel" Output: "e" Example 2: Input: $s = "Weekly", $t = "Weeakly" Output: "a" Example 3: Input: $s = "Box", $t = "Boxy" Output: "y"

Logic

Count character frequencies in both strings. In Perl, increment a hash for every character in $s and decrement it for every character in $t; the single character whose net count equals -1 is the added character. In Python, build two collections.Counter maps and return the character whose count in t exceeds its count in s. Both approaches run in O(n) time and O(k) space, where k is the alphabet size.

Perl Solution (ch-1.pl)

#!/usr/bin/env perl
use v5.38;
use warnings;
use Type::Params -sigs;
use Types::Standard qw(Str);
use Test::More;

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

sub find_odd_character ( $s, $t ) {
    my %count;
    $count{$_}++ for split //, $s;
    $count{$_}-- for split //, $t;

    for my $char ( sort keys %count ) {
        return $char if $count{$char} == -1;
    }

    return '';
}

Python Solution (ch-1.py)

def find_odd_character(s: str, t: str) -> str:
    """Return the additional character present in string t compared to s."""
    count_s = Counter(s)
    count_t = Counter(t)

    for char, count in count_t.items():
        if count > count_s.get(char, 0):
            return char

    return ""

Task 2: Most Frequent Word

You are given a paragraph $p and a banned word $w. Write a script to return the most frequent word that is not banned.

Examples

Example 1: Input: $p = "Joe hit a ball, the hit ball flew far after it was hit." $w = "hit" Output: "ball" The banned word "hit" occurs 3 times. The other word "ball" occurs 2 times. Example 2: Input: $p = "Perl and Raku belong to the same family. Perl is the most popular language in the weekly challenge." $w = "the" Output: "Perl" The banned word "the" occurs 3 times. The other word "Perl" occurs 2 times.

Logic

Extract word tokens from the paragraph using \w+. Normalize each token to lowercase for case-insensitive comparison against the banned word and frequency counting, while recording the first-seen original casing so that words like "Perl" retain their proper capitalization in the output. Finally, select the non-banned word with the highest frequency in O(n) time (or O(u log u) for sorting unique words in Perl).

Perl Solution (ch-2.pl)

#!/usr/bin/env perl
use v5.38;
use warnings;
use Type::Params -sigs;
use Types::Standard qw(Str);
use Test::More;

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

sub most_frequent_word ( $p, $w ) {
    my $banned = lc $w;
    my %word_count;
    my %original;

    for my $word ( $p =~ /(\w+)/g ) {
        my $key = lc $word;
        next if $key eq $banned;
        $original{$key} //= $word;
        $word_count{$key}++;
    }

    my ($most_frequent) =
        sort { $word_count{$b} <=> $word_count{$a} || $a cmp $b }
        keys %word_count;

    return defined $most_frequent ? $original{$most_frequent} : '';
}

Python Solution (ch-2.py)

def most_frequent_word(p: str, w: str) -> str:
    """Return the most frequent non-banned word in paragraph p."""
    banned = w.lower()
    word_count: Counter[str] = Counter()
    original: dict[str, str] = {}

    for word in re.findall(r"\w+", p):
        key = word.lower()
        if key == banned:
            continue
        original.setdefault(key, word)
        word_count[key] += 1

    if not word_count:
        return ""

    most_frequent = word_count.most_common(1)[0][0]
    return original[most_frequent]