RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved string alterations and analyses. (Note that this ends today.)

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.

This is basically a DFS, with minor variation. In Python, I start with a function to return the longest substring of a specific letter. (Not of any letter, because it's fractionally simpler to write this way.)

def lsub(wm, t):
  start = 0
  state = 0
  ll = []

Iterate through the characters (this is actually an array of chars, not a string, but in Python this part would work the same way).

  for n in range(len(wm)):

If we weren't in a run of the target character but are now, mark the starting point.

    if state == 0:
      if wm[n] == t:
        start = n
        state = 1
    else:

If we were in a run of the target character but we aren't now, note the length.

      if wm[n] != t:
        ll.append(n - start)
        state = 0

And if we were still in a run at the end, note that length too.

  if state == 1:
    ll.append(len(wm) - start)

Return the greatest length seen.

  return max(ll)

Then the main function:

def longestrepeatingcharacter(st, k):

Split the input string into characters, and derive a list of unique ones.

  origin = list(st)
  targets = set(origin)
  longestsub = 0

Run through each possible target with a DFS (current string as array, number of changes so far).

  for t in targets:
    queue = deque()
    queue.append([origin, 0])
    while len(queue) > 0:
      wm, ct = queue.popleft()

Look for the most repetitions of the target character.

      longestsub = max(longestsub, lsub(wm, t))

If we have changes left,

      if ct < k:
        ctp = ct + 1

For each position in the string that isn't currently the target, generate a new entry that has that character changed to the target.

        for n in range(len(wm)):
          if wm[n] != t:
            wmp = wm.copy()
            wmp[n] = t
            queue.append([wmp, ctp])

then return the longest run we saw.

  return longestsub

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.

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'

Lots of splitting needed. Here's the Perl.

sub longestabsolutepath($fs) {
  my @components;
  my $maxlen = 0;

The entries are separated by \\n.

  foreach my $entry (split /\\n/, $fs) {

The "parts" are a series of tabs then the actual name, but splitting on tab is an easy way to count them.

    my @parts = split /\\t/, $entry;

Minimum depth is 1.

    my $depth = scalar @parts;

Get the components stack to the right depth, and push on the length of the current item.

    while (scalar @components < $depth) {
      push @components, 0;
    }
    while (scalar @components >= $depth) {
      pop @components;
    }
    push @components, length($parts[-1]);

If it's a filename,

    if (index($parts[-1], '.') > -1) {

Extract the total length of this pathname (assume a 1-character path separator).

      $maxlen = max($maxlen, sum(@components) + scalar @components - 1);
    }
  }
  $maxlen;
}

Full code in all tagged languages is on codeberg.