Weekly Challenge: The longest

Weekly Challenge 399

Each week Mohammad S. Anwar sends out The Weekly Challenge, a chance for all of us to come up with solutions to two weekly tasks. My solutions are written in Python first, and then converted to Perl. Unless otherwise stated, Copilot (and other AI tools) have NOT been used to generate the solution. It's a great way for us all to practice some coding.

Challenge, My solutions

Task 1: Longest Repeating Character

You are given a string str and an integer k > 0.

Write a script to choose any character of str and change it to another character. You may perform this operation up to k times. Return the length of the longest reachable substring of a single letter.

My solution

To start this solution, I set string_length to the length of input_string.

from collections import Counter

def longest_repeating_char(input_string: str, k: int) -> int:
    string_length = len(input_string)

I use a double loop. The outer loop is length starting with string_length decreasing to 1. The inner loop variable is start and represents the start position, from 0 to string_length - length.

    for length in range(string_length, 0, -1):
        for start in range(0, string_length - length + 1):

I generate substr which is the length characters starting at start. Next I calculate the most frequent letter, and store the number of occurrences in the max_freq variable.

            substr = input_string[start : start + length]
            max_freq = max(Counter(substr).values())

If max_freq plus k (the number of letters that can change) is equal or greater than length, I have the solution and return length. If it isn't the loop iterates again. If it is exhausted, I return 0. This should only occur if input_string is empty, as even a single letter and k of 1 should return a value.

            if max_freq + k >= length:
                return length

    return 0

The Perl solution follows the same logic. There isn't an equivalent of the Counter function, so I have a function called find_max_freq that achieves the same functionality.

use List::Util "max";

sub find_max_freq ($str) {
    my %freq = ();
    $freq{$_}++ foreach ( split //, $str );
    return max( values(%freq) );
}

sub main ( $input_string, $k ) {
    my $string_length = length($input_string);

    for ( my $length = $string_length ; $length > 0 ; $length-- ) {
        foreach my $start ( 0 .. $string_length - $length ) {
            my $substr = substr( $input_string, $start, $length );

            my $max_freq = find_max_freq($substr);

            if ( $max_freq + $k >= $length ) {
                say $length;
                return;
            }
        }
    }

    say 0;
}

Examples

$ ./ch-1.py AAAAA 5
5

$ ./ch-1.py ABCDE 5
5

$ ./ch-1.py AAABBBBAA 1
5

$ ./ch-1.py ABACADA 2
5

$ ./ch-1.py BAAABAAAA 1
8

Task 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.

My solution

As per the example, it is expected that new lines and tabs are those characters, rather than a literal backslash followed by a letter.

For this I start by setting current_path as an empty list (array in Perl), and longest_path to 0. I then iterate through each line, using regular expression to get the tabs (leading tab characters, if any) and file (rest of the string). I update the current_path list to the path this file represents. If file contains a dot, I update longest_path if it is greater than the current value.

    current_path = []
    longest_path = 0

    for line in paths.split("\n"):
        tabs, file = re.search(r"^(\t*)(.*)$", line).groups() # type: ignore
        path_pos = len(tabs)

        current_path = [*current_path[:path_pos], file]
        length = len("/".join(current_path))

        if "." in file and length > longest_path:
            longest_path = length

    return longest_path

The Perl solution follows the same logic.

Examples

In bash, using $'' means that \n and \t are replaced with new line and tab characters.

$ ./ch-2.py $'dir\n\tsubdir1\n\t\tsubsubdir1\n\tsubdir2'
0

$ ./ch-2.py $'file1.txt\nfile2.ext\na.png'
9

$ ./ch-2.py $'my documents\n\tproject v1.0\n\t\tnotes v1.txt\n\timage.png'
38

$ ./ch-2.py $'root\n\ta\n\t\tb\n\t\t\tc.txt\n\td\n\t\te.txt'
14

$ ./ch-2.py $'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