The Weekly Challenge 256

Maximum Pairs & Merge Strings

Official Challenge • Solutions on GitHub

Task 1: Maximum Pairs

You are given an array of distinct words, @words. Write a script to find the maximum pairs in the given array. The words $words[i] and $words[j] can be a pair if one is the reverse of the other.

Examples

Example 1: Input: @words = ("ab", "de", "ed", "bc") Output: 1 There is one pair in the given array: "de" and "ed" Example 2: Input: @words = ("aa", "ba", "cd", "ed") Output: 0 Example 3: Input: @words = ("uv", "qp", "st", "vu", "mn", "pq") Output: 2

Logic

Store all distinct words in a hash/set for O(1) lookup. For each word, compute its reverse and check whether it differs from the word itself (so a palindrome does not pair with itself) and exists in the set. Each valid pair is counted twice (once from each direction), so dividing the total match count by 2 yields the exact number of pairs in O(n · L) time, where L is the average word length.

Perl Solution (ch-1.pl)

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

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

sub max_pairs ($words) {
    my %word_set = map { $_ => 1 } @$words;
    my $count    = 0;
    for my $word (@$words) {
        my $reversed = reverse $word;
        $count++ if $reversed ne $word && exists $word_set{$reversed};
    }
    return int( $count / 2 );
}

Python Solution (ch-1.py)

def max_pairs(words: list[str] | tuple[str, ...]) -> int:
    """Return the maximum number of reverse pairs in the distinct word list."""
    word_set = set(words)
    count = sum(1 for word in words if word[::-1] != word and word[::-1] in word_set)
    return count // 2

Task 2: Merge Strings

You are given two strings, $str1 and $str2. Write a script to merge the given strings by adding characters in alternating order starting with the first string. If one string is longer than the other, append the remaining characters at the end.

Examples

Example 1: Input: $str1 = "abcd", $str2 = "1234" Output: "a1b2c3d4" Example 2: Input: $str1 = "abc", $str2 = "12345" Output: "a1b2c345" Example 3: Input: $str1 = "abcde", $str2 = "123" Output: "a1b2c3de"

Logic

Iterate up to the length of the shorter string, appending one character from $str1 followed by one character from $str2 at each index. Once the shorter string is exhausted, append the remaining slice of the longer string. In Python, zip(str1, str2) handles the alternating pairing naturally, followed by slicing the remainder. Both implementations run in O(n + m) time and space.

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 merge_strings => (
    method     => 0,
    positional => [ Str, Str ],
);

sub merge_strings ( $str1, $str2 ) {
    my $len1   = length($str1);
    my $len2   = length($str2);
    my $min    = $len1 < $len2 ? $len1 : $len2;
    my $merged = '';
    for my $i ( 0 .. $min - 1 ) {
        $merged .= substr( $str1, $i, 1 ) . substr( $str2, $i, 1 );
    }
    $merged .= $len1 > $min ? substr( $str1, $min ) : substr( $str2, $min );
    return $merged;
}

Python Solution (ch-2.py)

def merge_strings(str1: str, str2: str) -> str:
    """Merge two strings by alternating characters and appending any remainder."""
    merged = "".join(a + b for a, b in zip(str1, str2))
    longer_part = str1[len(str2) :] if len(str1) > len(str2) else str2[len(str1) :]
    return merged + longer_part