This is my response to The Weekly Challenge #399.
Input: $str = "AAAAA", $k = 2
Output: 5
Every character in the string is already the same letter "A".
The maximum operations allowed (k = 2) do not even need to be used.
The entire string of length 5 is already the longest valid substring.
Example 2:
Input: $str = "ABCDE", $k = 4
Output: 5
All 5 characters in the string are distinct.
The most frequent character occurs only 1 time.
To turn the entire string into a single repeated character, we need to replace 5 - 1 = 4 characters.
Since k = 4, we can replace "B","C","D", and "E" with "A" to form "AAAAA".
Example 3:
Input: $str = "AAABBBBAA", $k = 1
Output: 5
If we target "A", we could change the "B" in "AAAB" (k=1 replacement) to get length 4 ("AAAA").
If we target "B", we can pick the substring "BBBBA" and change the single trailing "A" to "B" (k=1 replacement) to form "BBBBB", which gives a length of 5.
Targeting "B" gives better result than targeting "A".
Example 4:
Input: $str = "ABACADA", $k = 2
Output: 5
Look at the substring [0..4] which is "ABACA" (length 5).
In this window, "A" appears 3 times, and there are 2 non-"A" characters ("B" and "C").
With k = 2, we can replace "B" and "C" with "A" to form "AAAAA".
Look at the substring [2..6] which is "ACADA" (length 5).
Here, "A" appears 3 times, and non-"A" characters ("C" and "D") count to 2.
Replacing them gives "AAAAA".
In both cases, the maximum valid length is 5.
Example 5:
Input: $str = "BAAABAAAA", $k = 1
Output: 8
The string has two groups of "A"s separated by a single "B" ("AAABAAAA").
We can replace the character 4 "B" with an "A" to get a sequence of 8 "A".
#! /usr/bin/env raku
unit sub MAIN (Str $str where $str.chars > 0,
Int $k where $k > 0,
:v(:$verbose));
my @chars = $str.comb;
my $best = 0;
my $left = 0;
my %count;
for ^ @chars.elems -> $right
{
%count{@chars[$right]}++;
while $right - $left + 1 - %count.values.max > $k
{
%count{@chars[$left]}--;
$left++;
}
my $window = @chars[$left .. $right].join;
my $max-count = %count.values.max;
my $letter = %count.keys.first: { %count{$_} == $max-count };
my $changes = $window.chars - $max-count;
if $verbose
{
say ": \"$window\" — $max-count x $letter, $changes \
replacement" ~ ($changes == 1 ?? '' !! 's');
}
$best = max($best, $window.chars);
}
say $best;
[7] A list of individual characters.
[8] The result, the length of the longest substring, will end up here.
[9] The start of the current substring lookup.
[10] All the characters and their count will be updated here.
[12] Iterate over all the indices in the array.
[14] Count the character.
[16] As long as the window needs more than $k replacements,
[18] • disregard the leftmost value
[19] • and move the left pointer to the right.
[22] The characters in the current window, as a single string.
[23] Get the frequency of the most frequent character.
[24] Get that character. The keys part gives all
the characters, and we use first to grep out the first one that matches
the given expression; i.e. has that frequency.
See docs.raku.org/routine/first for more information about first.
[25] Compute the number of changes.
[33] Do we have a new best value? If so, update it.
[36] Print the result.
Running it:
$ ./longest-repeating-character AAAAA 2
5
$ ./longest-repeating-character ABCDE 4
5
$ ./longest-repeating-character AAABBBBAA 1
5
$ ./longest-repeating-character ABACADA 2
5
$ ./longest-repeating-character BAAABAAAA 1
8
Looking good.
With verbose mode:
$ ./longest-repeating-character -v AAAAA 2
: "A" — 1 x A, 0 replacements
: "AA" — 2 x A, 0 replacements
: "AAA" — 3 x A, 0 replacements
: "AAAA" — 4 x A, 0 replacements
: "AAAAA" — 5 x A, 0 replacements
5
$ ./longest-repeating-character -v ABCDE 4
: "A" — 1 x A, 0 replacements
: "AB" — 1 x B, 1 replacement
: "ABC" — 1 x B, 2 replacements
: "ABCD" — 1 x B, 3 replacements
: "ABCDE" — 1 x B, 4 replacements
5
$ ./longest-repeating-character -v AAABBBBAA 1
: "A" — 1 x A, 0 replacements
: "AA" — 2 x A, 0 replacements
: "AAA" — 3 x A, 0 replacements
: "AAAB" — 3 x A, 1 replacement
: "ABB" — 2 x B, 1 replacement
: "ABBB" — 3 x B, 1 replacement
: "ABBBB" — 4 x B, 1 replacement
: "BBBBA" — 4 x B, 1 replacement
: "BAA" — 2 x A, 1 replacement
5
$ ./longest-repeating-character -v ABACADA 2
: "A" — 1 x A, 0 replacements
: "AB" — 1 x B, 1 replacement
: "ABA" — 2 x A, 1 replacement
: "ABAC" — 2 x A, 2 replacements
: "ABACA" — 3 x A, 2 replacements
: "ACAD" — 2 x A, 2 replacements
: "ACADA" — 3 x A, 2 replacements
5
$ ./longest-repeating-character -v BAAABAAAA 1
: "B" — 1 x B, 0 replacements
: "BA" — 1 x A, 1 replacement
: "BAA" — 2 x A, 1 replacement
: "BAAA" — 3 x A, 1 replacement
: "AAAB" — 3 x A, 1 replacement
: "AAABA" — 4 x A, 1 replacement
: "AAABAA" — 5 x A, 1 replacement
: "AAABAAA" — 6 x A, 1 replacement
: "AAABAAAA" — 7 x A, 1 replacement
8
This shows the window after each step, with the dominant letter and the number of replacements the window needs.
Input: $fs = "dir\n\tsubdir1\n\t\tsubsubdir1\n\tsubdir2"
Output: 0
There are no files in the system (a file must contain a . character separating a name and extension).
Since there are no files, the answer is 0.
Example 2:
Input: $fs = "file1.txt\nfile2.ext\na.png"
Output: 9
All entries are located at root depth (0 tabs).
Found File Paths:
"file1.txt" (length = 9)
"file2.ext" (length = 9)
"a.png" (length = 5)
The longest absolute file path length is 9.
Example 3:
Input: $fs = "my documents\n\tproject v1.0\n\t\tnotes v1.txt\n\timage.png"
Output: 38
Notice project v1.0 is a directory (it has children beneath it), while notes v1.txt and image.png are files.
Found File Paths:
"my documents/project v1.0/notes v1.txt" (length = 38)
"my documents/image.png" (length = 22)
The maximum absolute length is 38.
Example 4:
Input: $fs = "root\n\ta\n\t\tb\n\t\t\tc.txt\n\td\n\t\te.txt"
Output: 14
Found File Paths:
"root/a/b/c.txt" => 4 + 1 + 1 + 1 + 1 + 1 + 5 = 14
"root/d/e.txt" => 4 + 1 + 1 + 1 + 5 = 12
The longest file path is "root/a/b/c.txt" with length 14.
Example 5:
Input: $fs = "a\n\tb\n\t\tc\n\t\t\td\n\t\t\t\te.txt\n\tvery_long_directory_name\n\t\tf.txt"
Output: 32
Found File Paths:
"a/b/c/d/e.txt" => 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 5 = 13
"a/very_long_directory_name/f.txt" => 1 + 1 + 24 + 1 + 5 = 32
The long directory name compensates for depth, giving a max length of 32.
#! /usr/bin/env raku
unit sub MAIN (Str $fs is copy where $fs.chars > 0,
:v(:$verbose));
$fs = $fs.subst(/\\n/, "\n", :g).subst(/\\t/, "\t", :g);
my @lines = $fs.split: /\n/;
my @depth = @lines.map: { .comb(/\t/).elems };
my @name = @lines.map: { .subst(/^ \t* /, '') };
my @dir;
my $best = 0;
for ^ @lines.elems -> $i
{
my $d = @depth[$i];
my $name = @name[$i];
my $next-depth = $i + 1 < @lines.elems ?? @depth[$i + 1] !! -1;
if $name.contains('.') && $next-depth <= $d
{
my $path = (|@dir[0 .. $d - 1], $name).join: '/';
say ": $name => $path ({ $path.chars })" if $verbose;
$best = max($best, $path.chars);
}
else
{
@dir[$d] = $name;
say ": $name (directory)" if $verbose;
}
}
say $best;
[3] The is copy part is there so that changing the variable (in [6])
works.
[6] Replace newlines with \n, and tabs with \t.
[8] Get the lines (split on \n).
[9] Get the depth for each line; the number of leading tabs.
[10] Get the names, without the leading tab(s).
[12] The directory names, used by verbose mode only.
[13] The currently longest path.
[15] Iterate over the indices in the array.
[17] The dept of the current path.
[18] The name.
[19] The dept of the next path, if any. We err to -1 if we are at the
end already.
[21] Is this a file? Using contains is more efficient
than a regex when we do as simple lookup as this.
See docs.raku.org/routine/contains for more information about contains.
[23] Get the full path by joining al the directories (in the path) and adding the filename.
[25] Do we have a new best value? If so, update it.
[27] It is not a file, i.e. it is a (new) directory.
[28] Add it to the list of directories in the current path.
[34] Print the result.
Running it:
$ ./longest-absolute-path 'dir\n\tsubdir1\n\t\tsubsubdir1\n\tsubdir2'
0
$ ./longest-absolute-path 'file1.txt\nfile2.ext\na.png'
9
$ ./longest-absolute-path 'my documents\n\tproject v1.0\n\t\tnotes v1.txt\n\timage.png'
38
$ ./longest-absolute-path 'root\n\ta\n\t\tb\n\t\t\tc.txt\n\td\n\t\te.txt'
14
$ ./longest-absolute-path 'a\n\tb\n\t\tc\n\t\t\td\n\t\t\t\te.txt\n\tvery_long_directory_name\n\t\tf.txt'
32
Looking good.
With verbose mode:
$ ./longest-absolute-path -v 'dir\n\tsubdir1\n\t\tsubsubdir1\n\tsubdir2'
: dir (directory)
: subdir1 (directory)
: subsubdir1 (directory)
: subdir2 (directory)
0
$ ./longest-absolute-path -v 'file1.txt\nfile2.ext\na.png'
: file1.txt => file1.txt (9)
: file2.ext => file2.ext (9)
: a.png => a.png (5)
9
$ ./longest-absolute-path -v 'my documents\n\tproject v1.0\n\t\tnotes v1.txt\n\timage.png'
: my documents (directory)
: project v1.0 (directory)
: notes v1.txt => my documents/project v1.0/notes v1.txt (38)
: image.png => my documents/image.png (22)
38
$ ./longest-absolute-path -v 'root\n\ta\n\t\tb\n\t\t\tc.txt\n\td\n\t\te.txt'
: root (directory)
: a (directory)
: b (directory)
: c.txt => root/a/b/c.txt (14)
: d (directory)
: e.txt => root/d/e.txt (12)
14
$ ./longest-absolute-path -v 'a\n\tb\n\t\tc\n\t\t\td\n\t\t\t\te.txt\n\tvery_long_directory_name\n\t\tf.txt'
: a (directory)
: b (directory)
: c (directory)
: d (directory)
: e.txt => a/b/c/d/e.txt (13)
: very_long_directory_name (directory)
: f.txt => a/very_long_directory_name/f.txt (32)
32
And that's it.