Peter Campbell Smith

Good strings and hidden sequences

Weekly challenge 221 — 12 June 2023

Week 221 - 12 Jun 2023

Task 1

Task — Good strings

You are given a list of @words and a string $chars. A string is good if it can be formed by characters from $chars; each character can be used only once. Write a script to return the sum of lengths of all good strings in words.


From the examples it would appear that the intention is that each letter in $chars can only be used once in each word, rather than only once in all the words. I also assumed that we should treat upper and lower case letters as being equivalent.

I create %letters, where $letter{$k} is a count of the letters $k in $chars. For example, in Mohammad's first example $chars is 'atach', so $letters{'a'} == 2 and $letters{'t'} == 1 and so on.

Then for each word in @words I take a fresh copy of %letters and do this:

next WORD unless $letters{$letter}; $letters{$letter} --;

If the word survives that, then I add its length to $length and add the word itself to $explain.

Try it 

@words - example: cat, bt, hat, tree

$chars - example: achat



use v5.16;    # The Weekly Challenge - 2023-06-12
use utf8;     # Week 221 task 1 - Good strings
use strict;   # Peter Campbell Smith
use warnings; # Blog:

good_strings(['cat', 'bt', 'hat', 'tree'], 'atach');
good_strings(['hello', 'world', 'challenge'], 'welldonehopper');
good_strings([qw(A string is good if it can be formed by characters from chars each character can be used only once)], 
good_strings(['one', 'two', 'three'], 'xyz');

sub good_strings {
    my (@words, $chars, $letter, %letters, $word, $length, $explain, %all_letters);
    @words = @{$_[0]};
    $chars = lc($_[1]);
    $length = 0;
    $explain = '';
    # split $chars into individual letters
    for $letter (split('', $chars)) {
        $all_letters{$letter} ++;
    WORD: for $word (@words) {
        # unused letters
        %letters = %all_letters;
        # disregard words that have any letters not in $chars
        for $letter (split('', lc($word))) {
            next WORD unless $letters{$letter};
            $letters{$letter} --;
        # we have a good word
        $length += length($word);
        $explain .= qq[$word + ];
    say qq[\nInput:  \@words = ('] . join(qq[', '], @words) . qq['), \$chars = '$chars'];
    say qq[Output: $length = ] . substr($explain, 0, -2);


Input:  @words = ('cat', 'bt', 'hat', 'tree'), $chars = 'atach'
Output: 6 = cat + hat

Input:  @words = ('hello', 'world', 'challenge'), $chars = 'welldonehopper'
Output: 10 = hello + world

Input:  @words = ('A', 'string', 'is', 'good', 'if', 'it', 'can', 'be', 'formed', 'by', 'characters', 'from', 'chars', 'each', 'character', 'can', 'be', 'used', 'only', 'once'), $chars = 'abcdefghijklmnopqrstuvwxyz'
Output: 56 = A + string + is + if + it + can + be + formed + by + from + chars + each + can + be + used + only + once

Input:  @words = ('one', 'two', 'three'), $chars = 'xyz'
Output: 0 =