The weekly challenge 392 - Task 2: Words Length Product

 1 #!/usr/bin/env perl
 2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-392/#TASK2
 3 #
 4 # Task 2: Words Length Product
 5 # ============================
 6 #
 7 # You are given an array of strings.
 8 #
 9 # Write a script to return the maximum value of len($words[i]) * len($words[j])
10 # where the two words do not share common letters. If no such two words exist,
11 # return 0.
12 #
13 ## Example 1
14 ##
15 ## Input: @words = ("a", "ab", "abc", "d", "de", "def")
16 ## Output: 9
17 ##
18 ## Two words are "abc" and "def".
19 #
20 ## Example 2
21 ##
22 ## Input: @words = ("a", "aa", "aaa", "aaaa")
23 ## Output: 0
24 ##
25 ## Since no two words can be chosen without sharing letters, the result is 0.
26 #
27 ## Example 3
28 ##
29 ## Input: @words = ("meet", "app", "code", "sky", "bold")
30 ## Output: 16
31 ##
32 ## Two words are "meet" and "bold".
33 #
34 ## Example 4
35 ##
36 ## Input: @words = ("a", "ab", "abc", "abcd", "efghi")
37 ## Output: 20
38 ##
39 ## Two words are "abcd" and "efghi".
40 #
41 ## Example 5
42 ##
43 ## Input: @words = ("xyz", "w", "abcdefg", "hij")
44 ## Output: 21
45 ##
46 ## Two words are "abcdefg" and "hij".
47 #
48 ############################################################
49 ##
50 ## discussion
51 ##
52 ############################################################
53 #
54 # We check each word against each other. If they have no common letters,
55 # we can multiply their lengths and keep the maximum so far.
56 
57 use v5.36;
58 
59 words_length_product("a", "ab", "abc", "d", "de", "def");
60 words_length_product("a", "aa", "aaa", "aaaa");
61 words_length_product("meet", "app", "code", "sky", "bold");
62 words_length_product("a", "ab", "abc", "abcd", "efghi");
63 words_length_product("xyz", "w", "abcdefg", "hij");
64 
65 sub words_length_product(@words) {
66     say "Input: (" . join(", ", map { "\"$_\"" } @words) . ")";
67     my $max = 0;
68     foreach my $i (0..$#words) {
69         foreach my $j ($i+1..$#words) {
70             next if has_common_chars($words[$i], $words[$j]);
71             my $this_length_product = length($words[$i]) * length($words[$j]);
72             $max = $this_length_product if $this_length_product > $max;
73         }
74     }
75     say "Output: $max";
76 }
77 
78 sub has_common_chars($word1, $word2) {
79     foreach my $char1 (split //, $word1) {
80         foreach my $char2 (split //, $word2) {
81             return 1 if $char1 eq $char2;
82         }
83     }
84     return 0;
85 }
86