Longest substrings without repeating characters
Given a string, find the longest substring without any repeating characters.
- Task
Julia
Works on any array, treating a character string as a character array. <lang julia>function alluniquehead(arr)
len = length(arr) if len > 1 for i in 2:len if arr[i] in @view arr[1:i-1] return arr[1:i-1] end end end return arr[:]
end
function maxuniques(arr)
length(arr) < 2 && return arr amax = [alluniquehead(@view arr[i:end]) for i in 1:length(arr)] maxlen = maximum(map(length, amax)) return filter(a -> length(a) == maxlen, amax)
end
for s in ["xyzyabcybdfd", "xyzyab", "zzzzz", "a", "α⊆϶α϶", "", [1, 2, 3, 4, 1, 2, 5, 6, 1, 7, 8, 1, 0]]
uarray = maxuniques(collect(s)) !isempty(uarray) && length(uarray[1]) > 1 && uarray[1][1] isa Char && (uarray = String.(uarray)) println("\"$s\" => ", uarray)
end
</lang>
- Output:
"xyzyabcybdfd" => ["zyabc", "cybdf"] "xyzyab" => ["zyab"] "zzzzz" => [['z'], ['z'], ['z'], ['z'], ['z']] "a" => ['a'] "α⊆϶α϶" => ["α⊆϶", "⊆϶α"] "" => Char[] "[1, 2, 3, 4, 1, 2, 5, 6, 1, 7, 8, 1, 0]" => [[3, 4, 1, 2, 5, 6], [2, 5, 6, 1, 7, 8]]
Python
The following algorithm works but is not terribly efficient for long strings. <lang python>def longest_substring(s = "xyzyab"):
substr = [s[x:y] for x in range(len(s)) for y in range(x+1, len(s) + 1)] no_reps = [] for sub in substr: if len(sub) == len(set(sub)) and sub not in no_reps: no_reps.append(sub) max_len = max(len(sub) for sub in no_reps) if no_reps else 0 max_subs = [sub for sub in no_reps if len(sub) == max_len] return max_subs
if __name__ == '__main__':
for s in ["xyzyabcybdfd", "xyzyab", "zzzzz", "a", "α⊆϶α϶", "", [1, 2, 3, 4, 1, 2, 5, 6, 1, 7, 8, 1, 0]]: print(f"{s} => {longest_substring(s)}")
</lang>
- Output:
xyzyabcybdfd => ['zyabc', 'cybdf'] xyzyab => ['zyab'] zzzzz => ['z'] a => ['a'] α⊆϶α϶ => ['α⊆϶', '⊆϶α'] => [] [1, 2, 3, 4, 1, 2, 5, 6, 1, 7, 8, 1, 0] => [[3, 4, 1, 2, 5, 6], [2, 5, 6, 1, 7, 8]]
Raku
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. <lang perl6>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; $start += 1 + $sub.index($next); } } @substr[$end - $start].push: $string.substr($start); @substr.pairs.tail
}
- Standard tests
say "\nOriginal string: {abbreviate $_}\nLongest substring(s) chars: ", .&longest
for flat qww<xyzyabcybdfd xyzyab zzzzz a >,
- multibyte Unicode
'👒🎩🎓👩👩👦👦🧢🎓👨👧👧👒👩👩👦👦🎩🎓👒🧢',
- check a file
slurp 'unixdict.txt';</lang>
- 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: (abbreviated) 10th 1st 2nd 3rd 4th 5th 6th 7th 8t ... rian zounds zucchini zurich zygote Longest substring(s) chars: 15 => [mbowel disgrunt]
REXX
<lang rexx>/*REXX pgm finds the longest substring (in a given string) without a repeating character*/ parse arg $ /*obtain optional argument from the CL.*/ if $== | $=="," then $= 'xyzyabcybdfd' /*Not specified? Then use the default.*/ L= length($) /*L: the length of the given string.*/ maxL= 0 /*MAXL: max length substring (so far).*/ @.= /*array to hold the max len substrings.*/
do j=1 for L; b= substr($, j, 1) /*search for max length substrings. */ x= /*X: the substring, less the 1st char*/ do k=j+1 to L; x= x || substr($, k, 1) /*search for the max length substrings.*/ if \okx(x) then iterate j /*Are there an replications? Skip it. */ _= length(x); if _<maxL then iterate /*is length less then the current max? */ @._= @._ x; maxL= _ /*add this substring to the max list. */ end /*k*/ end /*j*/
say 'longest substring's(words(@.maxL)) "in " $ ' ───► ' @.maxL exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ s: if arg(1)==1 then return arg(3); return word(arg(2) 's', 1) /*simple pluralizer*/ /*──────────────────────────────────────────────────────────────────────────────────────*/ OKx: procedure; parse arg y; do r=1 for length(y)-1 /*look for duplicate chars.*/
if pos(substr(y, r, 1), y, r+1)>0 then return 0 end /*r*/; return 1</lang>
- output when using the default input:
longest substrings in xyzyabcybdfd ───► zyabc cybdf
Ring
<lang ring> see "working..." + nl see "Longest substrings without repeating characters are:" + nl str = "xyzyabcybdfd" see "Input: " + str + nl lenStr = len(str) strOk = [] lenOk = 0
for n = 1 to lenStr
for m = 1 to lenStr-n+1 temp = substr(str,n,m) add(strOk,temp) next
next
for n = len(strOk) to 1 step -1
if len(strOK[n]) = 1 del(strOK,n) ok
next
for n = 1 to len(strOK)
for m = 1 to len(strOK)-1 if len(strOK[m+1]) > len(strOK[m]) temp = strOK[m] strOK[m] = strOK[m+1] strOK[m+1] = temp ok next
next
for n = 1 to len(strOK)
flag = 1 for m = 1 to len(strOK[n]) for p = m+1 to len(strOK[n]) if strOK[n][m] = strOK[n][p] flag = 0 exit ok next next if flag = 1 if len(strOK[n]) >= lenOk see "len = " + len(strOK[n]) + " : " + strOK[n] + nl lenOK = len(strOK[n]) ok ok
next
see "done..." + nl </lang>
- Output:
working... Longest substrings without repeating characters are: Input: xyzyabcybdfd len = 5 : zyabc len = 5 : cybdf done...
Wren
<lang ecmascript>import "/seq" for Lst
var substrings = Fn.new { |s|
var n = s.count if (n == 0) return [""] var ss = [] for (i in 0...n) { for (len in 1..n-i) ss.add(s[i...i+len]) } return ss
}
System.print("The longest substring(s) of the following without repeating characters are:\n") var strs = ["xyzyabcybdfd", "xyzyab", "zzzzz", "a", "", ] for (s in strs) {
var longest = [] var longestLen = 0 for (ss in substrings.call(s)) { if (Lst.distinct(ss.toList).count == ss.count) { if (ss.count >= longestLen) { if (ss.count > longestLen) { longest.clear() longestLen = ss.count } longest.add(ss.join()) } } }
longest = Lst.distinct(longest) System.print("String = '%(s)'") System.print(longest) System.print("Length = %(longest[0].count)\n")
}</lang>
- Output:
The longest substring(s) of the following without repeating characters are: String = 'xyzyabcybdfd' [zyabc, cybdf] Length = 5 String = 'xyzyab' [zyab] Length = 4 String = 'zzzzz' [z] Length = 1 String = 'a' [a] Length = 1 String = '' [] Length = 0