Words length product

You are given an array of strings. Write a script to return the maximum value of length($words[$i]) * length($words[$j]) where the two words do not share common letters. If no such two words exist, return 0.

Examples

Example 1
Input: @words = ('a', 'ab', 'abc', 'd', 'de', 'def')
Output: 9
Two words are 'abc' and 'def'.

Example 2
Input: @words = ('a', 'aa', 'aaa', 'aaaa')
Output: 0
Since no two words can be chosen without sharing letters, the result
   is 0.

Example 3
Input: @words = ('meet', 'app', 'code', 'sky', 'bold')
Output: 16
Two words are 'meet' and 'bold'.

Example 4
Input: @words = ('a', 'ab', 'abc', 'abcd', 'efghi')
Output: 20
Two words are 'abcd' and 'efghi'.

Example 5
Input: @words = ('xyz', 'w', 'abcdefg', 'hij')
Output: 21
Two words are 'abcdefg' and 'hij'.

Analysis

My solution works like this.

For each word in the input I create a $map[$j]. The map is a binary number with bit 0 set to 1 if the word contains (one or more) 'a', bit 1 if it has a 'b' and so on up to bit 25 if it has a 'z'.

I can then quickly find where words $i and $j have a letter in common, because if they do, $map[$i] & $map[$j] is non-zero. (That '&' is a binary AND operator).

So I work through all the possible pairs of words, and when I find a pair where the '&' operation returns zero, I check the product of the words' lengths to see whether it's the largest so far.

Despite there being two pairs of nested loops, this is a pretty efficient solution. The last example I have given - taken from the description of today's featured picture by Wikipedia - contains 78 words but still completes in well under a second.

Try it 

Your input:

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2026-09-21
use utf8;     # Week 392 - task 2 - Words length product
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

words_length_product('a', 'ab', 'abc', 'd', 'de', 'def');
words_length_product('a', 'aa', 'aaa', 'aaaa');
words_length_product('meet', 'app', 'code', 'sky', 'bold');
words_length_product('a', 'ab', 'abc', 'abcd', 'efghi');
words_length_product('xyz', 'w', 'abcdefg', 'hij');
words_length_product(qw[Vertumnus is an oil painting by the Italian 
artist Giuseppe Arcimboldo depicting Rudolf II Holy Roman Emperor as 
Vertumnus the Roman god of changing seasons gardens fruit trees and 
plant growth Rudolfs portrait is composed of fruits vegetables and 
flowers and combines visual humour with political allegory presenting
him as a ruler possessing harmony with and power over nature Seized
by Swedish forces after the Thirty Years War the painting is now held
at Skokloster Castle in Sweden]);

sub words_length_product {
    
    my (@words, $a, $j, @map, $c, $w, $best, $best_words, $i, $score);
    
    # initialise
    @words = @_;
    $a = ord('a');
    
    # create bitmap of letters used in each word
    for $j (0 .. $#words) {
        $w = lc($words[$j]);
        $map[$j] = 0;
        for $c (split('', $words[$j])) {
            $map[$j] |= (1 << (ord($c) - $a));
        }
    }
    
    # find best pair of words not sharing a letter
    $best = $score = 0;
    for $i (0 .. $#words - 1) {
        for $j ($i + 1 .. $#words) {
            next if ($map[$i] & $map[$j]);
            $score = length($words[$i]) * length($words[$j]);

            # found a potential winner!
            if ($score > $best) {
                $best = $score;
                $best_words = qq['$words[$i]', '$words[$j]'];
            }
        }
    }
    
    # report
    say qq[\nInput:  '] . join(q[', '], @words) . q['];
    say qq[Output: $best] . ($best > 0 ? qq[ - $best_words] : '');
}

19 lines of code

Output from script

Input:  'a', 'ab', 'abc', 'd', 'de', 'def'
Output: 9 - 'abc', 'def'

Input:  'a', 'aa', 'aaa', 'aaaa'
Output: 0

Input:  'meet', 'app', 'code', 'sky', 'bold'
Output: 16 - 'meet', 'bold'

Input:  'a', 'ab', 'abc', 'abcd', 'efghi'
Output: 20 - 'abcd', 'efghi'

Input:  'xyz', 'w', 'abcdefg', 'hij'
Output: 21 - 'xyz', 'abcdefg'

Input:  'Vertumnus', 'is', 'an', 'oil', 'painting', 'by', 'the',
   'Italian', 'artist', 'Giuseppe', 'Arcimboldo', 'depicting',
   'Rudolf', 'II', 'Holy', 'Roman', 'Emperor', 'as', 'Vertumnus',
   'the', 'Roman', 'god', 'of', 'changing', 'seasons', 'gardens',
   'fruit', 'trees', 'and', 'plant', 'growth', 'Rudolfs', 'portrait',
   'is', 'composed', 'of', 'fruits', 'vegetables', 'and', 'flowers',
   'and', 'combines', 'visual', 'humour', 'with', 'political',
   'allegory', 'presenting', 'him', 'as', 'a', 'ruler', 'possessing',
   'harmony', 'with', 'and', 'power', 'over', 'nature', 'Seized',
   'by', 'Swedish', 'forces', 'after', 'the', 'Thirty', 'Years',
   'War', 'the', 'painting', 'is', 'now', 'held', 'at', 'Skokloster',
   'Castle', 'in', 'Sweden'
Output: 80 - 'changing', 'Skokloster'