| 13 November 2026 | Challenge 399 |
Absolute Repetitions
Last week I realized that J source syntax highlighting is supported in GitHub Pages. Due to a misconfiguration in my local Jekyll instance it did not show up, which was consistent with J not being mentioned in the list of supported languages. Therefore I didn’t even provide the seemingly useless language tag. After recognizing my fault I enabled the highlighting in all of my previous posts containing J source code.
Task 1: Longest Repeating Character
Submitted by: Mohammad Sajid Anwar
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.
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".
Solution
An infix of a string can be transformed into a repeated single character by at most k changes, if there are at most k characters different from the most frequent character.
Looping over infixes with decreasing size and stopping at the first infix that can be transformed accordingly solves the task.
Perl
use strict;
use warnings;
use experimental 'signatures';
use List::Util qw(max pairvalues);
use List::MoreUtils 'frequency';
sub lrc ($str, $k) {
my $l = length $str;
for (my $i = $l; $i; $i--) {
for my $j (0 .. $l - $i) {
return $i if $i <= $k + max pairvalues
frequency split //, substr $str, $j, $i;
}
}
}
See the full solution to task 1.
J
There is a little technical difficulty with the usage of the “infix” adverb /: Its operand must be a monad because the derived verb is a dyad using its left argument as the infix size.
However, the infixes shall be checked against the number of permitted changes, which requires a dyad.
This issue can be solved by defining an adverb having the number of permitted changes as left noun operand. Bonding a noun to a dyad transforms it into a monad, which can be used as operand to the “infix” adverb.
NB. Create a verb that finds the longest repeated character
NB. reachable with m changes.
lrc =: adverb define
NB. - Count the frequency of each item in y.
NB. - Substract the maximum frequency from the length.
NB. The result is the number of changes required
NB. to make all items equal to the most frequent item.
NB. - Check if the number from the previous step
NB. does not exceed the given x.
can_eq =. [ >: #@] - [: >./ #/.~@]
NB. - Apply u to all infixes of y having a size of x.
NB. - Return x if any call to u returns 1 or
NB. x - 1 otherwise.
try_infix =. [`-`[:`-.`[:`(+./)`(]:\)`:6
NB. Try infixes of y in decreasing size and
NB. stop if all items can be made equal
NB. using the current size.
] (m&can_eq try_infix~ f.)^:_ # : [:
)
NB. A verb that uses its x-argument as lrc's m-operand:
lrcv =: dyad def 'x lrc y'
See the full solution.
Task 2: Longest Absolute Path
Submitted by: Mohammad Sajid Anwar
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.
Solution
The task may be divided into some independent steps:
- create paths from the file system representation
- identify paths representing a file
- find the maximum path length
The first step is the most interesting. I’ll consider two different approaches:
- Create a file system tree from its string representation and identify all paths using a depth-first traversal.
- Starting at the deepest level, replace every tab with the preceding name at the same level until all tabs are resolved.
Perl
Following the first approach.
Processing the string representation line-wise as an in-memory file and incrementally create the file system tree.
Recursively traverse the tree in depth-first order.
use strict;
use warnings;
use experimental 'signatures';
use List::Util qw(max sum);
sub scan_fs ($fs) {
use autodie;
my $root = {name => '', parent => undef, children => []};
my $lvl = 0;
my $current = $root;
open my $fsh, '<', \$fs;
while (<$fsh>) {
my ($head, $name) = /^(\t*)(.*)/;
my $new_lvl = length $head;
if ($new_lvl > $lvl) {
$current = $current->{children}[-1];
$lvl = $new_lvl;
} elsif ($new_lvl < $lvl) {
while ($new_lvl < $lvl) {
$current = $current->{parent};
$lvl--;
}
}
my $new = {name => $name, parent => $current, children => []};
push $current->{children}->@*, $new;
}
close $fsh;
$root;
}
sub leaf_paths ($root) {
my @files;
for my $child ($root->{children}->@*) {
push @files, [$root->{name}, @$_] for __SUB__->($child)->@*;
}
@files ? [@files] : [[$root->{name}]];
}
sub longest_abs_path ($fs) {
my $root = scan_fs ($fs);
my $leaves = leaf_paths($root);
max(map @$_ - 2 + sum(map length, @$_),
grep $_->[-1] =~ /\./, $leaves->@*) // 0;
}
See the full solution to task 2.
J
Following the second approach.
Though it is easy to say “starting at the deepest level”, it is not so trivial to implement. A program will naturally start from the highest level, but the order may be reversed by recursion.
After all, this approach is not so different from the first. It’s like building a temporary tree while traversing it.
NB. Find the longest path in a file system represented by y.
longest_path =: _(adverb define)
NB. Split y at newlines into boxed items and
NB. split items at tabs into boxed subitems.
NB. Produces an empty box for each tab.
to_boxed =. (<;._1 L:0) @ ((TAB , ]) L:0) @ (<;._2 L:0) @ ((LF ,~ ]) L:0)
NB. Partition y into intervals with start positions
NB. defined by 1's in x.
part =. ;.1
NB. Check if an entry is a top-level, i.e. if is a singleton
top =. 1&=@#@>
NB. Drop the first item from y and the first sub-item from all
NB. remaining items.
sub =. }.&.>@}.
NB. Complete y depending on its size:
NB. - box y if it is empty
NB. - pass y if it is a singleton
NB. - process y recursively if it contains multiple items
complete =. <`]`$:@.((0 1)&I.@#)
NB. Join the boxed content of x with the boxed content of each item from y
NB. and box the result.
join =. <@:,&.>"_ 0
NB. Pick the first item from y.
head =. {.
NB. Remove outer boxes.
raze =. ;
NB. - Partition y into intervals where each interval starts with
NB. a top-level element.
NB. - Build the sub structure for each interval
NB. - Complete the sub structure
NB. - Join the first item of y with the results from the previous step.
NB. - Remove outer boxes.
get_paths =. ([: raze top (head join complete f. @: sub) part ]) $::
NB. Select paths having a dot in their trailing sub-item.
get_files =. ] #~ '.' e. S:0 [: {: L:1 ]
NB. Path length: Sum over the lengths of all path parts
NB. plus the number of separators
length =. ([: <: # S:1 + [: +/ # S:0)"0
NB. find the maximum over all elements from y and zero.
max0 =. 0&>. @ (>./)
NB. All steps like pearls on a string:
max0 @: length @ get_files @ get_paths @ to_boxed f. : [:
)
See the full solution.