Completing the time and

levelling the letters

Weekly challenge 194 — 7 December 2022

Week 194 - 7 Dec 2022

Task 2

You are given a string made of alphabetic characters only, a-z. Write a script to determine whether removing only one character can make the frequency of the remaining characters the same.

Example 1: Input: $s = 'abbc' Output: 1 since removing one alphabet 'b' will give us 'abc' where each alphabet frequency is the same.Example 2: Input: $s = 'xyzyyxz' Output: 1 since removing 'y' will give us 'xzyyxz'.Example 3: Input: $s = 'xzxz' Output: 0 since removing any one alphabet would not give us string with same frequency alphabet.

*This is a reworking of my original solution.*

There are 3 classes of strings where the removal of a single character leaves the frequency of all the remaining characters the same:

- One character appears n times and any others appear n - 1 times (including n == 0, ie all the characters are the same)
- One character appears once and all the others appear n times
- All the characters are unique, ie all appear once

My solution first calculates the frequency of each character and then considers each of the above cases. If the string does not fall into one of these, then there is no solution.

I use a labelled `for`

loop to consider the 3 cases. In each case, if the
test succeeds I set `$result`

and then do `last CASE`

. If the
test fails I do `next CASE`

to consider any remaining cases.

Lastly, if
`$result`

has not been set, there is no solution.

I have coded this as a for loop over the 3 cases, as I thought that was clearer, but it coulkd equally be done with three nested if clauses.

Finally, although the above is an efficient solution, perhaps a more convincing, if slower, solution would be simply to delete each character in turn, and see if the remaiing characters all appear equally often.

#!/usr/bin/perl # Peter Campbell Smith - 2022-12-06 # PWC 194 task 2 use v5.28; use utf8; use warnings; # what about all the chars are the same? my (@tests, $test, @chars, $char, %freq, $max_freq, $max_char, $result, $case, $seen_one); @tests = ('aabbbcc', 'deeffgg', 'hijklm', 'xxyyyz', 'uuvvvwww', 'uuuuuvvvwww', 't', 'tttt'); for $test (@tests) { %freq = (); $max_freq = 0; return unless $test; # create $freq{'x'} as frequency of 'x' in string @chars = split(//, $test); for $char (@chars) { $freq{$char} ++; } # find the maximum frequency and the (or one of the) characters having that frequency for $char (keys %freq) { if ($freq{$char} > $max_freq) { $max_freq = $freq{$char}; $max_char = $char; } } $result = ''; CASE: for $case (1 .. 3 ) { # case 1: for each char that isn't $max_char, the frequency must be $max_freq - 1 if ($case == 1) { for $char (sort keys %freq) { next CASE if ($char ne $max_char and $freq{$char} != $max_freq - 1); } $result = qq[1 as removal of one '$max_char' leaves the remaining frequencies equal]; last CASE; # case 2: one char has freq == 1 and the rest have the same freq } elsif ($case == 2) { next CASE if $max_freq == 1; $seen_one = ''; for $char (sort keys %freq) { if ($freq{$char} == 1 and $seen_one eq '') { $seen_one = $char; } else { next CASE if ($freq{$char} != $max_freq); } } next CASE unless $seen_one; $result = qq[1 as removal of '$seen_one' leaves the remaining frequencies equal]; last CASE; # case 3: all chars have freq 1 } else { for $char (sort keys %freq) { last CASE if $freq{$char} != 1; } $result = qq[1 as removal of any character leaves the remaining frequencies equal]; } } $result = qq[0 as no single removal leaves the remaining frequencies equal] unless $result; # report result say qq[\nInput: $test\nOutput: $result]; }

Input: aabbbcc Output: 1 as removal of one 'b' leaves the remaining frequencies equal Input: deeffgg Output: 1 as removal of 'd' leaves the remaining frequencies equal Input: hijklm Output: 1 as removal of any character leaves the remaining frequencies equal Input: xxyyyz Output: 0 as no single removal leaves the remaining frequencies equal Input: uuvvvwww Output: 0 as no single removal leaves the remaining frequencies equal Input: uuuuuvvvwww Output: 0 as no single removal leaves the remaining frequencies equal Input: t Output: 1 as removal of one 't' leaves the remaining frequencies equal Input: tttt Output: 1 as removal of one 't' leaves the remaining frequencies equal

Peter Campbell Smith is hereby placed in the public domain