Perl Weekly Challenge: Week 399
Challenge 1:
Longest Repeating Character
You are given a string
strand an integerk> 0.Write a script to choose any character of
strand change it to another character. You may perform this operation up toktimes. Return the length of the longest reachable substring of a single letter.
Example 1
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".
We can solve this problem by using the "sliding window" technique. First we need some setup.
We split the input string into an array of characters.
my @chars = $str.comb;
We define a Hash to use as a frequency table. Its' keys will be individual characters and values, the number of times the character occurs in a window.
my %frequency;
$maxcount will store the longest character frequency seen.
my $maxCount = 0;
And longestLength will store the length of the longest reachable substring of
a single character.
my $longestLength = 0;
The last variable needed is an index into the array which marks the left edge of the sliding window.
my $left = 0;
Now we can begin iterating through each character. As well as the $character itself,
we get its' index in @chars to use as the $right edge of the sliding window.
for @chars.kv -> $right, $char {
The frequency table is updated.
%frequency{$char}++;
if the frequnct of the current character is greater than $maxCount, it becomes
the new value of $maxCount.
$maxCount = max($maxCount, %frequency{$char});
As long as more than $k characters need replacement, we shrink the size of
the window.
while $right - $left + 1 - $maxCount > $k {
my $leftChar = @chars[$left];
%frequency{$leftChar}--;
$left++;
}
If the length of the window is greater than $longestLength, it becomes the
new value of $longestLength.
$longestLength = max($longestLength, $right - $left + 1);
}
After all characters have been traversed, we print thr value of $longestLength.
say $longestLength;
For the perl version, we have to provide our own equivalent to max().
my @chars = split //, $str;
my %frequency;
my $maxCount = 0;
my $longestLength = 0;
my $left = 0;
for my ($right, $char) (indexed @chars) {
$frequency{$char}++;
$maxCount = max($maxCount, $frequency{$char});
while ($right - $left + 1 - $maxCount > $k) {
my $leftChar = $chars[$left];
$frequency{$leftChar}--;
$left++;
}
$longestLength = max($longestLength, $right - $left + 1);
}
say $longestLength;
Challenge 2:
Longest Absolute Path
You are given a filesystem as string.
Write a script to return the length of the longest absolute path to a file in the abstracted file system. If there is no file in the system, return 0.
dir
- subdir1
- file1.ext
- subsubdir1
- subdir2
- subsubdir2
- file2.ext
The above filesystem can be represented as below:
"dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"
Example 1
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.
We have to recreate the file tree from the string $fs we are given. One way
to do this is by substituting the literal characters '\t' and '\n' with tabs
and newlines and then splitting the string on newlines to make an array.
Each element of the array will be a possibly indented file or directory name.
my @entries = $fs.subst('\n', "\n", :g).subst('\t', "\t", :g).lines;
We store the names and the depth in the file tree they are at in two arrays. The depth is calculated by the amount of indentation.
my @names;
my @depths;
for @entries -> $entry {
$entry ~~ /^(\t*)(.*)$/;
@depths.push($0.chars);
@names.push(~$1);
}
One more array is needed for path lengths.
my @pathLengths;
The $longestPath found so far initially defaults to 0.
my $longestPath = 0;
Now we iterate through @names capturing the index of the element as well as the
name itself...
for @names.kv -> $index, $name {
...because the index is used to access the equivalent element in @depths.
my $depth = @depths[$index];
The length of the file or directory name is the initial value of $pathLength.
my $pathLength = $name.chars;
If the element is not the root of the file tree (i.e. the $depth is more than 0,)
the length of the parent path (plus 1 for the separator) is added to $pathLength.
if $depth > 0 {
$pathLength += @pathLengths[$depth - 1] + 1;
}
The $pathLength is added to our array @pathLengths.
@pathLengths[$depth] = $pathLength;
A dotted entry counld be a directory or a file. If it has no child entries we treat it as a file, otherwise as a directory.
my $hasChildren = $index + 1 < @entries.elems
&& @depths[$index + 1] > $depth;
If the entry is a file and the $pathLength is longer than the current value of
$longestPath, it becomes the new value of $longestPath.
if $name.contains('.') && !$hasChildren {
$longestPath = max($longestPath, $pathLength);
}
}
After traversing the file tree, iur final result is the value of $longestPath.
say $longestPath;
We need max() again for this one and a bit more regex work is involved to
substitute for .lines() and .contains but otherwise the Perl version is
very similiar.
$fs =~ s/\\n/\n/g;
$fs =~ s/\\t/\t/g;
my @entries = split /\n/, $fs;
my @names;
my @depths;
for my $entry (@entries) {
$entry =~ /^(\t*)(.*)$/;
push @depths, length $1;
push @names, $2;
}
my @pathLengths;
my $longestPath = 0;
for my ( $index, $name) (indexed @names) {
my $depth = $depths[$index];
my $pathLength = length $name;
if ($depth > 0) {
$pathLength += $pathLengths[$depth - 1] + 1;
}
$pathLengths[$depth] = $pathLength;
my $hasChildren = $index + 1 < scalar @entries
&& $depths[$index + 1] > $depth;
if ($name =~ /\./ && !$hasChildren) {
$longestPath = max($longestPath, $pathLength);
}
}
say $longestPath;