Longest substrings without repeating characters
Detects any character when checking for repeated characters, even multi-byte composite characters, control sequences and whitespace.
Note that there is no requirement that the substrings be unique, only that each has no repeated characters internally.
Not going to bother handling arrays since an array is not a string, and the task description specifically says 'Given a string'.
sub abbreviate ($_) { .chars > 80Β ?? "(abbreviated)\n" ~ .substr(0,35) ~ ' ... ' ~ .substr(*-35)Β !! $_ }
sub longest ($string) {
return 0 => [] unless $string.chars;
my ($start, $end, @substr) = 0, 0;
while ++$end < $string.chars {
my $sub = $string.substr($start, $end - $start);
if $sub.contains: my $next = $string.substr: $end, 1 {
@substr[$end - $start].push($sub) if $end - $start >= @substr.end;
$start += 1 + $sub.index($next);
}
}
@substr[$end - $start].push: $string.substr($start);
@substr.pairs.tail
}
# Testing
say "\nOriginal string: {abbreviate $_}\nLongest substring(s) chars: ", .&longest
# Standard tests
for flat qww< xyzyabcybdfd xyzyab zzzzz a '' >,
# multibyte Unicode
< ππ©ππ©βπ©βπ¦βπ¦π§’ππ¨βπ§βπ§ππ©βπ©βπ¦βπ¦π©πππ§’ Ξ±βΟΆΞ±ΟΆ >,
# check a file
slurp 'unixdict.txt';
Output:
Original string: xyzyabcybdfd
Longest substring(s) chars: 5 => [zyabc cybdf]
Original string: xyzyab
Longest substring(s) chars: 4 => [zyab]
Original string: zzzzz
Longest substring(s) chars: 1 => [z z z z z]
Original string: a
Longest substring(s) chars: 1 => [a]
Original string:
Longest substring(s) chars: 0 => []
Original string: ππ©ππ©βπ©βπ¦βπ¦π§’ππ¨βπ§βπ§ππ©βπ©βπ¦βπ¦π©πππ§’
Longest substring(s) chars: 6 => [π§’ππ¨βπ§βπ§ππ©βπ©βπ¦βπ¦π©]
Original string: Ξ±βΟΆΞ±ΟΆ
Longest substring(s) chars: 3 => [Ξ±βΟΆ βΟΆΞ±]
Original string: (abbreviated)
10th
1st
2nd
3rd
4th
5th
6th
7th
8t ... rian
zounds
zucchini
zurich
zygote
Longest substring(s) chars: 15 => [mbowel
disgrunt]
Last updated
Was this helpful?