Longest substrings without repeating characters: Difference between revisions
(Added Easylang) |
|||
(39 intermediate revisions by 22 users not shown) | |||
Line 3: | Line 3: | ||
;Task: |
;Task: |
||
Given a string, find the '''longest substring''' without any repeating characters. |
Given a string, find the '''longest substring''' without any repeating characters. |
||
{{Template:Strings}} |
|||
<br><br> |
<br><br> |
||
=={{header|11l}}== |
|||
{{trans|Python: Some optimisation}} |
|||
<syntaxhighlight lang="11l">F longest_substring2(s) |
|||
V max_subs = [s[0.<1]] * 0 |
|||
V mx = 0 |
|||
L(x) 0 .< s.len |
|||
L(y) x + 1 .. s.len |
|||
V sub = s[x .< y] |
|||
I y - x >= mx & sub.len == Set(Array(sub)).len |
|||
I y - x == mx & sub !C max_subs |
|||
max_subs.append(sub) |
|||
E |
|||
max_subs = [sub] |
|||
mx = y - x |
|||
R max_subs |
|||
L(s) [‘xyzyabcybdfd’, ‘xyzyab’, ‘zzzzz’, ‘a’, ‘’] |
|||
print(s‘ => ’longest_substring2(s)) |
|||
V arr = [1, 2, 3, 4, 1, 2, 5, 6, 1, 7, 8, 1, 0] |
|||
print(arr‘ => ’longest_substring2(arr))</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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]] |
|||
</pre> |
|||
=={{header|Action!}}== |
|||
<syntaxhighlight lang="action!">BYTE FUNC GetLength(CHAR ARRAY s BYTE start) |
|||
BYTE ARRAY tab(256) |
|||
BYTE i |
|||
CHAR c |
|||
Zero(tab,256) |
|||
i=start |
|||
WHILE i<=s(0) |
|||
DO |
|||
c=s(i) |
|||
tab(c)==+1 |
|||
IF tab(c)>1 THEN |
|||
EXIT |
|||
FI |
|||
i==+1 |
|||
OD |
|||
RETURN (i-start) |
|||
PROC LongestSubstrings(CHAR ARRAY s) |
|||
CHAR ARRAY tmp(256) |
|||
BYTE count,maxLen,i,len |
|||
IF s(0)=0 THEN |
|||
RETURN |
|||
FI |
|||
i=1 maxLen=0 |
|||
FOR i=1 TO s(0) |
|||
DO |
|||
len=GetLength(s,i) |
|||
IF len>maxLen THEN |
|||
maxLen=len |
|||
FI |
|||
OD |
|||
count=0 |
|||
FOR i=1 TO s(0) |
|||
DO |
|||
len=GetLength(s,i) |
|||
IF len=maxLen THEN |
|||
IF count>0 THEN |
|||
Print(", ") |
|||
FI |
|||
SCopyS(tmp,s,i,i+maxlen-1) |
|||
PrintF("""%S""",tmp) |
|||
count==+1 |
|||
FI |
|||
OD |
|||
RETURN |
|||
PROC Test(CHAR ARRAY s) |
|||
PrintF("Input: ""%S""%E",s) |
|||
Print("Result: [") |
|||
LongestSubstrings(s) |
|||
PrintE("]") PutE() |
|||
RETURN |
|||
PROC Main() |
|||
Test("xyzyabcybdfd") |
|||
Test("xyzyab") |
|||
Test("zzzzz") |
|||
Test("a") |
|||
Test("thisisastringtest") |
|||
Test("") |
|||
RETURN</syntaxhighlight> |
|||
{{out}} |
|||
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Longest_substrings_without_repeating_characters.png Screenshot from Atari 8-bit computer] |
|||
<pre> |
|||
Input: "xyzyabcybdfd" |
|||
Result: ["zyabc", "cybdf"] |
|||
Input: "xyzyab" |
|||
Result: ["zyab"] |
|||
Input: "zzzzz" |
|||
Result: ["z", "z", "z", "z", "z"] |
|||
Input: "a" |
|||
Result: ["a"] |
|||
Input: "thisisastringtest" |
|||
Result: ["astring", "ringtes"] |
|||
Input: "" |
|||
Result: [] |
|||
</pre> |
|||
=={{header|Ada}}== |
|||
<syntaxhighlight lang="ada">with Ada.Text_IO; |
|||
procedure Longest_Substring is |
|||
function Longest (Item : String) return String is |
|||
Hist : array (Character) of Natural := (others => 0); |
|||
First : Natural := Item'First; |
|||
Last : Natural := Item'First - 1; |
|||
Longest_First : Natural := Item'First; |
|||
Longest_Last : Natural := Item'First - 1; |
|||
procedure Adjust is |
|||
begin |
|||
if Last - First > Longest_Last - Longest_First then |
|||
Longest_First := First; |
|||
Longest_Last := Last; |
|||
end if; |
|||
end Adjust; |
|||
begin |
|||
if Item = "" then |
|||
return Item; |
|||
end if; |
|||
for Index in Item'Range loop |
|||
Last := Index; |
|||
Hist (Item (Index)) := Hist (Item (Index)) + 1; |
|||
if Hist (Item (Index)) = 1 then |
|||
Adjust; |
|||
else |
|||
for A in First .. Index loop |
|||
if (for all E of Hist => E <= 1) then |
|||
First := A; |
|||
Adjust; |
|||
exit; |
|||
end if; |
|||
Hist (Item (A)) := Hist (Item (A)) - 1; |
|||
end loop; |
|||
end if; |
|||
end loop; |
|||
return Item (Longest_First .. Longest_Last); |
|||
end Longest; |
|||
procedure Test (Item : String) is |
|||
use Ada.Text_IO; |
|||
begin |
|||
Put ("original : '"); Put (Item); Put_Line ("'"); |
|||
Put ("longest : '"); Put (Longest (Item)); Put_Line ("'"); |
|||
end Test; |
|||
begin |
|||
Test (""); |
|||
Test ("a"); |
|||
Test ("xyzyabcybdfd"); |
|||
Test ("thisisastringtest"); |
|||
Test ("zzzzz"); |
|||
end Longest_Substring;</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
original : '' |
|||
longest : '' |
|||
original : 'a' |
|||
longest : 'a' |
|||
original : 'xyzyabcybdfd' |
|||
longest : 'zyabc' |
|||
original : 'thisisastringtest' |
|||
longest : 'astring' |
|||
original : 'zzzzz' |
|||
longest : 'z' |
|||
</pre> |
|||
=={{header|APL}}== |
|||
{{works with|Dyalog APL}} |
|||
<syntaxhighlight lang="apl">lswrc←{ |
|||
sfx ← ⌽∘,¨,\∘⌽ |
|||
wrc ← ⊢(/⍨)⍳∘⍴(∧\=)⍳⍨ |
|||
ls ← ⊢(/⍨)(⌈/=⊢)∘(≢¨) |
|||
ls wrc¨ sfx ⍵ |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> lswrc¨ 'xyzyabcybdfd' 'xyzyab' 'zzzzz' 'a' '' |
|||
┌─────────────┬──────┬───────────┬───┬┐ |
|||
│┌─────┬─────┐│┌────┐│┌─┬─┬─┬─┬─┐│┌─┐││ |
|||
││cybdf│zyabc│││zyab│││z│z│z│z│z│││a│││ |
|||
│└─────┴─────┘│└────┘│└─┴─┴─┴─┴─┘│└─┘││ |
|||
└─────────────┴──────┴───────────┴───┴┘</pre> |
|||
=={{header|Arturo}}== |
|||
<syntaxhighlight lang="arturo">unrepeatableSubstrings: function [s][ |
|||
result: [["",0]] |
|||
if zero? s -> return [] |
|||
if one? s -> return @[s] |
|||
loop 0..dec size s 'a [ |
|||
if (a+1) =< dec size s [ |
|||
loop a..dec size s 'b [ |
|||
substr: to :string slice s a b |
|||
ss: size substr |
|||
if and? -> ss >= last maximum result 'x -> last x |
|||
-> substr = unique substr [ |
|||
result: (select result 'x -> ss = last x) ++ @[@[substr, ss]] |
|||
] |
|||
] |
|||
] |
|||
] |
|||
result: unique map result 'x -> first x |
|||
return result |
|||
] |
|||
loop ["xyzyabcybdfd", "xyzyab", "zzzzz", "a", ""] 'str -> |
|||
print [str "=> longest unrepeatable substring:" unrepeatableSubstrings str]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>xyzyabcybdfd => longest unrepeatable substring: [zyabc cybdf] |
|||
xyzyab => longest unrepeatable substring: [zyab] |
|||
zzzzz => longest unrepeatable substring: [z] |
|||
a => longest unrepeatable substring: [a] |
|||
=> longest unrepeatable substring: []</pre> |
|||
=={{header|AutoHotkey}}== |
|||
<syntaxhighlight lang="autohotkey">LSWRC(str){ |
|||
found := [], result := [], maxL := 0 |
|||
if (StrLen(str) = 1) |
|||
result[str] := true |
|||
else while (StrLen(str) >= 2){ |
|||
s := str |
|||
while StrLen(s) >= maxL{ |
|||
if !(s ~= "(.).*\1"){ |
|||
found[s] := true |
|||
maxL := maxL < StrLen(s) ? StrLen(s) : maxL |
|||
break |
|||
} |
|||
s := SubStr(s, 1, StrLen(s)-1) ; trim last chr |
|||
} |
|||
str := SubStr(str, 2) ; trim 1st chr and try again |
|||
} |
|||
maxL := 0 |
|||
for str in found |
|||
maxL := maxL < StrLen(str) ? StrLen(str) : maxL |
|||
for str in found |
|||
if (StrLen(str) = maxL) |
|||
result[str] := true |
|||
return result |
|||
}</syntaxhighlight> |
|||
Examples:<syntaxhighlight lang="autohotkey">db = |
|||
( |
|||
xyzyabcybdfd |
|||
xyzyab |
|||
zzz |
|||
a |
|||
) |
|||
for i, line in StrSplit(db, "`n", "`r"){ |
|||
result := "[", i := 0 |
|||
for str in LSWRC(line) |
|||
result .= str ", " |
|||
output .= line "`t> " Trim(result, ", ") "]`n" |
|||
} |
|||
MsgBox % output |
|||
return</syntaxhighlight> |
|||
{{out}} |
|||
<pre>xyzyabcybdfd > [cybdf, zyabc] |
|||
xyzyab > [zyab] |
|||
zzz > [z] |
|||
a > [a] |
|||
</pre> |
|||
=={{header|BCPL}}== |
|||
<syntaxhighlight lang="bcpl">get "libhdr" |
|||
// Fills up 'v' with words where w%0 is the start and w%1 is the end |
|||
// of each longest substring |
|||
let lswrc(s, v) = valof |
|||
$( let seen = vec 255 |
|||
let start = 1 and i = 1 and maxStart = 1 and maxEnd = 1 and n = 0 |
|||
for i=0 to 255 do i!seen := false |
|||
while i <= s%0 |
|||
$( test (s%i)!seen |
|||
while (s%i)!seen |
|||
$( (s%start)!seen := false |
|||
start := start + 1 |
|||
$) |
|||
or |
|||
$( (s%i)!seen := true |
|||
if i - start >= maxEnd - maxStart |
|||
$( maxStart := start |
|||
maxEnd := i |
|||
while n>0 & (v+n-1)%1 - (v+n-1)%0 < i-start |
|||
do n := n-1 |
|||
(v+n)%0 := start |
|||
(v+n)%1 := i |
|||
n := n+1 |
|||
$) |
|||
i := i + 1 |
|||
$) |
|||
$) |
|||
resultis n |
|||
$) |
|||
let substr(s, start, end, buf) = valof |
|||
$( buf%0 := end - start + 1 |
|||
for i = start to end do |
|||
buf%(i-start+1) := s%i |
|||
resultis buf |
|||
$) |
|||
let example(s) be |
|||
$( let v = vec 32 and b = vec 32 |
|||
let n = lswrc(s, v) |
|||
writef("Original string: '%s'*N", s) |
|||
writes("Longest substrings: ") |
|||
test n=0 do |
|||
writes("<empty>") |
|||
or for i = 0 to n-1 do |
|||
writef("'%s' ", substr(s, (v+i)%0, (v+i)%1, b)) |
|||
wrch('*N') |
|||
$) |
|||
let start() be |
|||
$( example("xyzyabcybdfd") |
|||
example("xyzyab") |
|||
example("zzzzz") |
|||
example("a") |
|||
example("") |
|||
$)</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Original string: 'xyzyabcybdfd' |
|||
Longest substrings: 'zyabc' 'cybdf' |
|||
Original string: 'xyzyab' |
|||
Longest substrings: 'zyab' |
|||
Original string: 'zzzzz' |
|||
Longest substrings: 'z' 'z' 'z' 'z' 'z' |
|||
Original string: 'a' |
|||
Longest substrings: 'a' |
|||
Original string: '' |
|||
Longest substrings: <empty></pre> |
|||
=={{header|BQN}}== |
|||
<syntaxhighlight lang="bqn">LongUniq ← ⌈´⊸=∘(≠¨)⊸/ ∧`∘∊⊸/¨∘↓</syntaxhighlight> |
|||
Alternative: |
|||
<syntaxhighlight lang="bqn">LongUniq ← ⊢´∘⊔∘(≠¨)⊸⊏ ∊⊸⊐⟜0⊸↑¨∘↓</syntaxhighlight> |
|||
Test: |
|||
<syntaxhighlight lang="bqn">LongUniq¨ "a"‿""‿"zzz"‿"xyzyab"‿"xyzyabcybdfd"</syntaxhighlight> |
|||
{{out}} |
|||
<pre>┌─ |
|||
· ⟨ "a" ⟩ ⟨ ⟨⟩ ⟩ ⟨ "z" "z" "z" ⟩ ⟨ "zyab" ⟩ ⟨ "zyabc" "cybdf" ⟩ |
|||
┘</pre> |
|||
=={{header|C}}== |
|||
<syntaxhighlight lang="c">#include <stdio.h> |
|||
#include <stdlib.h> |
|||
#include <string.h> |
|||
#include <stdbool.h> |
|||
struct substr { |
|||
const char *start; |
|||
size_t length; |
|||
}; |
|||
struct substr *lswrc(const char *str) { |
|||
size_t length = strlen(str); |
|||
struct substr *arr = malloc(sizeof(struct substr) * (length + 1)); |
|||
if (!arr) return NULL; |
|||
size_t start=0, i=0, maxStart=0, maxEnd=0, n=0; |
|||
bool used[256] = {false}; |
|||
for (i=0; i<length; i++) { |
|||
while (used[(unsigned char) str[i]]) |
|||
used[(unsigned char) str[start++]] = false; |
|||
used[(unsigned char) str[i]] = true; |
|||
if (i-start >= maxEnd-maxStart) { |
|||
maxStart = start; |
|||
maxEnd = i; |
|||
size_t len = maxEnd - maxStart + 1; |
|||
while (n>0 && arr[n-1].length < len) n--; |
|||
arr[n].start = &str[start]; |
|||
arr[n].length = len; |
|||
n++; |
|||
} |
|||
} |
|||
arr[n].start = NULL; |
|||
arr[n].length = 0; |
|||
return realloc(arr, sizeof(struct substr) * (n+1)); |
|||
} |
|||
int main() { |
|||
char *examples[] = {"xyzyabcybdfd", "xyzyab", "zzzzz", "a", "", NULL}; |
|||
for (size_t i=0; examples[i]; i++) { |
|||
printf("Original string: \"%s\"\n", examples[i]); |
|||
printf("Longest substrings: "); |
|||
struct substr *ls = lswrc(examples[i]); |
|||
for (size_t j=0; ls[j].start; j++) |
|||
printf("\"%.*s\" ", (int)ls[j].length, ls[j].start); |
|||
printf("\n"); |
|||
free(ls); |
|||
} |
|||
return 0; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Original string: "xyzyabcybdfd" |
|||
Longest substrings: "zyabc" "cybdf" |
|||
Original string: "xyzyab" |
|||
Longest substrings: "zyab" |
|||
Original string: "zzzzz" |
|||
Longest substrings: "z" "z" "z" "z" "z" |
|||
Original string: "a" |
|||
Longest substrings: "a" |
|||
Original string: "" |
|||
Longest substrings:</pre> |
|||
=={{header|C++}}== |
|||
<syntaxhighlight lang="cpp">#include <iostream> |
|||
#include <fstream> |
|||
#include <set> |
|||
#include <sstream> |
|||
#include <string> |
|||
#include <vector> |
|||
std::vector<std::string> longest_substrings_without_repeats(const std::string& str) { |
|||
size_t max_length = 0; |
|||
std::vector<std::string> result; |
|||
size_t length = str.size(); |
|||
for (size_t offset = 0; offset < length; ++offset) { |
|||
std::set<char> characters; |
|||
size_t len = 0; |
|||
for (; offset + len < length; ++len) { |
|||
if (characters.find(str[offset + len]) != characters.end()) |
|||
break; |
|||
characters.insert(str[offset + len]); |
|||
} |
|||
if (len > max_length) { |
|||
result.clear(); |
|||
max_length = len; |
|||
} |
|||
if (len == max_length) |
|||
result.push_back(str.substr(offset, max_length)); |
|||
} |
|||
return result; |
|||
} |
|||
void print_strings(const std::vector<std::string>& strings) { |
|||
std::cout << "["; |
|||
for (size_t i = 0, n = strings.size(); i < n; ++i) { |
|||
if (i > 0) |
|||
std::cout << ", "; |
|||
std::cout << '\'' << strings[i] << '\''; |
|||
} |
|||
std::cout << "]"; |
|||
} |
|||
void test1() { |
|||
for (std::string str : { "xyzyabcybdfd", "xyzyab", "zzzzz", "a", "thisisastringtest", "" }) { |
|||
std::cout << "Input: '" << str << "'\nResult: "; |
|||
print_strings(longest_substrings_without_repeats(str)); |
|||
std::cout << "\n\n"; |
|||
} |
|||
} |
|||
std::string slurp(std::istream& in) { |
|||
std::ostringstream out; |
|||
out << in.rdbuf(); |
|||
return out.str(); |
|||
} |
|||
void test2(const std::string& filename) { |
|||
std::ifstream in(filename); |
|||
if (!in) { |
|||
std::cerr << "Cannot open file '" << filename << "'.\n"; |
|||
return; |
|||
} |
|||
std::cout << "Longest substring with no repeats found in '" << filename << "': "; |
|||
print_strings(longest_substrings_without_repeats(slurp(in))); |
|||
std::cout << "\n"; |
|||
} |
|||
int main() { |
|||
test1(); |
|||
test2("unixdict.txt"); |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Input: 'xyzyabcybdfd' |
|||
Result: ['zyabc', 'cybdf'] |
|||
Input: 'xyzyab' |
|||
Result: ['zyab'] |
|||
Input: 'zzzzz' |
|||
Result: ['z', 'z', 'z', 'z', 'z'] |
|||
Input: 'a' |
|||
Result: ['a'] |
|||
Input: 'thisisastringtest' |
|||
Result: ['astring', 'ringtes'] |
|||
Input: '' |
|||
Result: [] |
|||
Longest substring with no repeats found in 'unixdict.txt': ['mbowel |
|||
disgrunt'] |
|||
</pre> |
|||
=={{header|EasyLang}}== |
|||
<syntaxhighlight> |
|||
func$[] longstr s$ . |
|||
subr maxtest |
|||
if len sub$ >= max |
|||
if len sub$ > max |
|||
max = len sub$ |
|||
max$[] = [ ] |
|||
. |
|||
max$[] &= sub$ |
|||
. |
|||
. |
|||
s$[] = strchars s$ |
|||
len empty[] 255 |
|||
len pos[] 255 |
|||
pos = 1 |
|||
while pos <= len s$[] |
|||
c = strcode s$[pos] |
|||
if pos[c] > 0 |
|||
maxtest |
|||
pos = pos[c] + 1 |
|||
pos[] = empty[] |
|||
sub$ = "" |
|||
c = strcode s$[pos] |
|||
. |
|||
pos[c] = pos |
|||
sub$ &= strchar c |
|||
pos += 1 |
|||
. |
|||
maxtest |
|||
return max$[] |
|||
. |
|||
for s$ in [ "xyzyabcybdfd" "xyzyab" "zzzzz" "a" "thisisastringtest" "" ] |
|||
print longstr s$ |
|||
. |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[ "zyabc" "cybdf" ] |
|||
[ "zyab" ] |
|||
[ "z" "z" "z" "z" "z" ] |
|||
[ "a" ] |
|||
[ "astring" "ringtes" ] |
|||
[ "" ] |
|||
</pre> |
|||
=={{header|Factor}}== |
|||
{{works with|Factor|0.99 2021-06-02}} |
|||
<syntaxhighlight lang="factor">USING: formatting grouping io kernel math sequences sets ; |
|||
: unique-substrings ( seq n -- newseq ) |
|||
tuck <clumps> [ cardinality = ] with filter ; |
|||
: longest-unique-substring ( seq -- newseq ) |
|||
dup length { } [ 2dup empty? swap 0 > and ] |
|||
[ drop 2dup unique-substrings [ 1 - ] dip ] while |
|||
2nip [ "" like ] map members ; |
|||
: test ( seq -- ) |
|||
dup longest-unique-substring "%u -> %u\n" printf ; |
|||
"Longest substrings without repeating characters:" print |
|||
{ "xyzyabcybdfd" "xyzyab" "zzzzz" "a" "" } [ test ] each</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Longest substrings without repeating characters: |
|||
"xyzyabcybdfd" -> { "zyabc" "cybdf" } |
|||
"xyzyab" -> { "zyab" } |
|||
"zzzzz" -> { "z" } |
|||
"a" -> { "a" } |
|||
"" -> { } |
|||
</pre> |
|||
=={{header|FreeBASIC}}== |
|||
<syntaxhighlight lang="freebasic">dim as string example = "antidisestablishmentarianism is a long word and so is flibbertigibbet." |
|||
function nrls( t as string ) as string |
|||
dim as integer best=0, best_length=-100, i=1, j, k, curr_length |
|||
dim as string c |
|||
for i = 1 to len(t)+1 |
|||
curr_length = 0 |
|||
for j = i+1 to len(t)+1 |
|||
curr_length += 1 |
|||
c = mid(t, j, 1) |
|||
for k = i to j - 1 |
|||
if c = mid(t, k, 1) then goto nexti |
|||
next k |
|||
next j |
|||
nexti: |
|||
if curr_length > best_length then |
|||
best_length = curr_length |
|||
best = i |
|||
end if |
|||
next i |
|||
return mid(t, best, best_length) |
|||
end function |
|||
print ">";nrls(example);"<" |
|||
print ">";nrls("My spoon is too big.");"<" |
|||
print ">";nrls("Rosetta Code.");"<" |
|||
print ">";nrls("AAAAA");"<" |
|||
print ">";nrls("abcdefghijklmnopqrstuvwxyz");"<" |
|||
print ">";nrls("aaa aeiou uuu");"<" |
|||
</syntaxhighlight> |
|||
{{out}}<pre> |
|||
>blishmentar< |
|||
>My spo< |
|||
>ta Code.< |
|||
>A< |
|||
>abcdefghijklmnopqrstuvwxyz< |
|||
> aeiou< |
|||
</pre> |
|||
=={{header|FutureBasic}}== |
|||
<syntaxhighlight lang="future basic"> |
|||
local fn substrings( t as CFStringRef ) |
|||
int beg, c, f, rpt, max = 0 |
|||
for beg = 0 to len(t) - 1 |
|||
rpt = instr( beg+1, t, mid(t, beg, 1), NSCaseInsensitiveSearch ) |
|||
if rpt < 0 then rpt = len(t) |
|||
c = beg + 1 |
|||
while c < rpt |
|||
f = instr(c + 1, t, mid(t, c, 1), NSCaseInsensitiveSearch) |
|||
if f < 0 then f = len(t) else if f < rpt then rpt = f |
|||
c++ |
|||
wend |
|||
if rpt - beg < max then continue |
|||
if rpt - beg > max then max = rpt - beg : mda_clear |
|||
mda_add(0) = mid(t, beg, max) |
|||
next |
|||
print @"\n The string: \"";t;@"\"\n Substring/s: "; |
|||
for c = 0 to mda_count(0) -1 |
|||
print @"\"";mda(c);@"\" "; |
|||
next |
|||
print |
|||
end fn |
|||
window 1, @"Longest Substring/s Without Repeated Letters" |
|||
fn substrings(@"xyzyabcybdfd") |
|||
fn substrings(@"thisisastringtest") |
|||
fn substrings(@"My spoon is too big.") |
|||
fn substrings(@"Rosetta Code") |
|||
fn substrings(@"AaAaA") |
|||
fn substrings(@"abcdefghijklmnopqrstuvwxyz") |
|||
fn substrings(@"aaa aeiou uuu") |
|||
fn substrings(@"abcdABCD") |
|||
handleevents |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
[[File:Longest Substrings without Repeated Letters.png]] |
|||
=={{header|Go}}== |
|||
{{trans|Wren}} |
|||
<syntaxhighlight lang="go">package main |
|||
import "fmt" |
|||
func substrings(s string) []string { |
|||
n := len(s) |
|||
if n == 0 { |
|||
return []string{""} |
|||
} |
|||
var ss []string |
|||
for i := 0; i < n; i++ { |
|||
for le := 1; le <= n-i; le++ { |
|||
ss = append(ss, s[i:i+le]) |
|||
} |
|||
} |
|||
return ss |
|||
} |
|||
func distinctRunes(chars []rune) []rune { |
|||
m := make(map[rune]bool) |
|||
for _, char := range chars { |
|||
m[char] = true |
|||
} |
|||
var l []rune |
|||
for k := range m { |
|||
l = append(l, k) |
|||
} |
|||
return l |
|||
} |
|||
func distinctStrings(strings []string) []string { |
|||
m := make(map[string]bool) |
|||
for _, str := range strings { |
|||
m[str] = true |
|||
} |
|||
var l []string |
|||
for k := range m { |
|||
l = append(l, k) |
|||
} |
|||
return l |
|||
} |
|||
func main() { |
|||
fmt.Println("The longest substring(s) of the following without repeating characters are:\n") |
|||
strs := []string{"xyzyabcybdfd", "xyzyab", "zzzzz", "a", ""} |
|||
for _, s := range strs { |
|||
var longest []string |
|||
longestLen := 0 |
|||
for _, ss := range substrings(s) { |
|||
if len(distinctRunes([]rune(ss))) == len(ss) { |
|||
if len(ss) >= longestLen { |
|||
if len(ss) > longestLen { |
|||
longest = longest[:0] |
|||
longestLen = len(ss) |
|||
} |
|||
longest = append(longest, ss) |
|||
} |
|||
} |
|||
} |
|||
longest = distinctStrings(longest) |
|||
fmt.Printf("String = '%s'\n", s) |
|||
fmt.Println(longest) |
|||
fmt.Printf("Length = %d\n\n", len(longest[0])) |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|J}}== |
|||
Implementation:<syntaxhighlight lang="j">longnorep=: {{ |
|||
c=. #y |
|||
while. ss=. c ]\ y do. |
|||
cnt=. #@~."1 ss |
|||
if. c e. cnt do. ~.ss#~ c=cnt return. end. |
|||
c=. c-1 |
|||
end. |
|||
}}</syntaxhighlight> |
|||
Examples: |
|||
<syntaxhighlight lang="j"> longnorep 'xyzyabcybdfd' |
|||
zyabc |
|||
cybdf |
|||
longnorep 'xyzyab' |
|||
zyab |
|||
longnorep 'zzzzz' |
|||
z |
|||
longnorep '' |
|||
longnorep 'astring' |
|||
astring |
|||
longnorep 'thisisastringtest' |
|||
astring |
|||
ringtes |
|||
longnorep 'Thequickbrownfoxjumpsoverthelazydog' |
|||
Thequickbrownf</syntaxhighlight> |
|||
This also works on sequences of numbers (though the character representation of the sequences of numbers may contain repeated characters, the represented numbers will not contain repetitions): |
|||
<syntaxhighlight lang="j"> longnorep 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</syntaxhighlight> |
|||
=={{header|jq}}== |
|||
'''Adapted from [[#Julia|Julia]]''' |
|||
{{works with|jq}} |
|||
'''Works with gojq, the Go implementation of jq''' |
|||
<syntaxhighlight lang="jq"># Use a dictionary for speed in case of very long strings |
|||
def alluniquehead: |
|||
length as $n |
|||
| if $n <= 1 then . |
|||
else . as $in |
|||
| {ix: -1} |
|||
| until(.i or (.ix == $n); |
|||
.ix += 1 |
|||
| $in[.ix:.ix+1] as $x |
|||
| if .dict[$x] then .i = .ix |
|||
else .dict[$x] = true |
|||
end ) |
|||
| $in[: .ix] |
|||
end ; |
|||
def maximal_substring_with_distinct_characters: |
|||
. as $in |
|||
| length as $n |
|||
| {i: -1} |
|||
| until( .i == $n or .stop; |
|||
.i += 1 |
|||
| if .max and .max > $n - .i then .stop = true |
|||
else ($in[.i:] | alluniquehead) as $head |
|||
| if ($head|length) > .max |
|||
then .ans = $head |
|||
| .max = ($head|length) |
|||
else . |
|||
end |
|||
end) |
|||
| .ans; |
|||
</syntaxhighlight> |
|||
'''Test Cases''' |
|||
<syntaxhighlight lang="jq">"xyzyabcybdfd", |
|||
"xyzyab", |
|||
"zzzzz", |
|||
"a", "α⊆϶α϶", |
|||
"" |
|||
| "\"\(.)\" => \"\(maximal_substring_with_distinct_characters)\"" |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
"xyzyabcybdfd" => "zyabc" |
|||
"xyzyab" => "zyab" |
|||
"zzzzz" => "z" |
|||
"a" => "a" |
|||
"α⊆϶α϶" => "α⊆϶" |
|||
"" => "" |
|||
</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
Works on any array, treating a character string as a character array. |
Works on any array, treating a character string as a character array. |
||
< |
<syntaxhighlight lang="julia">function alluniquehead(arr) |
||
len = length(arr) |
len = length(arr) |
||
if len > 1 |
if len > 1 |
||
Line 32: | Line 904: | ||
println("\"$s\" => ", uarray) |
println("\"$s\" => ", uarray) |
||
end |
end |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
"xyzyabcybdfd" => ["zyabc", "cybdf"] |
"xyzyabcybdfd" => ["zyabc", "cybdf"] |
||
Line 41: | Line 913: | ||
"" => Char[] |
"" => 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]] |
"[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]] |
||
</pre> |
|||
=={{header|Miranda}}== |
|||
<syntaxhighlight lang="miranda">main :: [sys_message] |
|||
main = [ Stdout (show test ++ " -> " ++ show (lswrc test) ++ "\n") |
|||
| test <- tests] |
|||
tests :: [[char]] |
|||
tests = ["xyzyabcybdfd", "xyzyab", "zzz", "a"] |
|||
lswrc :: [*]->[[*]] |
|||
lswrc s = nub [s' | s'<-noreps; #s' = maxlen] |
|||
where maxlen = max (map (#) noreps) |
|||
noreps = [norep (drop n s) | n<-[0..#s-1]] |
|||
norep = reverse . norep' [] |
|||
norep' mem [] = mem |
|||
norep' mem (a:as) = mem, if a $in mem |
|||
= norep' (a:mem) as, otherwise |
|||
in :: *->[*]->bool |
|||
in item [] = False |
|||
in item (a:as) = a = item \/ item $in as |
|||
nub :: [*]->[*] |
|||
nub = reverse . nub' [] |
|||
where nub' mem [] = mem |
|||
nub' mem (a:as) = nub' mem as, if a $in mem |
|||
= nub' (a:mem) as, otherwise</syntaxhighlight> |
|||
{{out}} |
|||
<pre>"xyzyabcybdfd" -> ["zyabc","cybdf"] |
|||
"xyzyab" -> ["zyab"] |
|||
"zzz" -> ["z"] |
|||
"a" -> ["a"]</pre> |
|||
=={{header|Modula-2}}== |
|||
<syntaxhighlight lang="modula2">MODULE LSWRC; |
|||
FROM InOut IMPORT WriteString, WriteLn; |
|||
FROM Strings IMPORT Length, Copy; |
|||
TYPE Range = |
|||
RECORD |
|||
start, length: CARDINAL; |
|||
END; |
|||
(* Returns start and length of every longest substring *) |
|||
PROCEDURE lswrc(in: ARRAY OF CHAR; VAR out: ARRAY OF Range): CARDINAL; |
|||
VAR i, num, start, strlen, len, maxStart, maxEnd: CARDINAL; |
|||
used: ARRAY [0..255] OF BOOLEAN; |
|||
BEGIN |
|||
FOR i := 0 TO 255 DO used[i] := FALSE; END; |
|||
strlen := Length(in); |
|||
start := 0; |
|||
maxStart := 0; |
|||
maxEnd := 0; |
|||
i := 0; |
|||
num := 0; |
|||
WHILE i < strlen DO |
|||
IF NOT used[ORD(in[i])] THEN |
|||
used[ORD(in[i])] := TRUE; |
|||
IF (i - start) >= (maxEnd - maxStart) THEN |
|||
maxStart := start; |
|||
maxEnd := i; |
|||
len := (maxEnd - maxStart + 1); |
|||
WHILE (num > 0) AND (out[num-1].length < len) DO |
|||
DEC(num); |
|||
END; |
|||
out[num].start := start; |
|||
out[num].length := len; |
|||
INC(num); |
|||
END; |
|||
INC(i); |
|||
ELSE |
|||
WHILE used[ORD(in[i])] DO |
|||
used[ORD(in[start])] := FALSE; |
|||
INC(start); |
|||
END; |
|||
END; |
|||
END; |
|||
RETURN num; |
|||
END lswrc; |
|||
PROCEDURE Example(s: ARRAY OF CHAR); |
|||
VAR buf: ARRAY [0..127] OF CHAR; |
|||
ranges: ARRAY [0..127] OF Range; |
|||
i, n: CARDINAL; |
|||
BEGIN |
|||
WriteString("Original string: "); |
|||
WriteString(s); |
|||
WriteLn(); |
|||
n := lswrc(s, ranges); |
|||
WriteString("Longest substrings: "); |
|||
IF n = 0 THEN |
|||
WriteString("<empty>"); |
|||
ELSE |
|||
FOR i := 0 TO n-1 DO |
|||
Copy(s, ranges[i].start, ranges[i].length, buf); |
|||
buf[ranges[i].length] := CHR(0); |
|||
WriteString(buf); |
|||
WriteString(" "); |
|||
END; |
|||
END; |
|||
WriteLn(); |
|||
END Example; |
|||
BEGIN |
|||
Example("xyzyabcybdfd"); |
|||
Example("xyzyab"); |
|||
Example("zzzzz"); |
|||
Example("a"); |
|||
Example(""); |
|||
END LSWRC.</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Original string: xyzyabcybdfd |
|||
Longest substrings: zyabc cybdf |
|||
Original string: xyzyab |
|||
Longest substrings: zyab |
|||
Original string: zzzzz |
|||
Longest substrings: z z z z z |
|||
Original string: a |
|||
Longest substrings: a |
|||
Original string: |
|||
Longest substrings: <empty></pre> |
|||
=={{header|Nim}}== |
|||
This version converts strings to sequences of runes. |
|||
<syntaxhighlight lang="nim">import sequtils, strutils, unicode |
|||
type Runes = seq[Rune] |
|||
func longestSubstrings(str: string): seq[string] = |
|||
var runes = str.toRunes |
|||
var current: Runes |
|||
var res: seq[Runes] # Result as a list of Runes. |
|||
var maxlen = 0 |
|||
for c in runes: |
|||
let idx = current.find(c) |
|||
if idx >= 0: |
|||
if current.len > maxlen: |
|||
res = @[current] |
|||
maxlen = current.len |
|||
elif current.len == maxlen and current notin res: |
|||
res.add current |
|||
current.delete(0, idx) |
|||
current.add c |
|||
# Process the last current string. |
|||
if current.len > maxlen: res = @[current] |
|||
elif current.len == maxlen and current notin res: res.add current |
|||
result = res.mapIt($it) |
|||
for str in ["xyzyabcybdfd", "xyzyab", "zzzzz", "a", "α⊆϶α϶", ""]: |
|||
echo '"', str, '"', " → ", longestSubstrings(str) |
|||
echo "\nLongest substrings in concatenated list of words from “unixdict.txt”: ", |
|||
longestSubstrings(toSeq("unixdict.txt".lines).join())</syntaxhighlight> |
|||
{{out}} |
|||
<pre>"xyzyabcybdfd" → @["zyabc", "cybdf"] |
|||
"xyzyab" → @["zyab"] |
|||
"zzzzz" → @["z"] |
|||
"a" → @["a"] |
|||
"α⊆϶α϶" → @["α⊆϶", "⊆϶α"] |
|||
"" → @[""] |
|||
Longest substrings in concatenated list of words from “unixdict.txt”: @["mboweldisgrunt"]</pre> |
|||
=={{header|Perl}}== |
|||
Gets the same answer that raku does when run against unixdict.txt |
|||
<syntaxhighlight lang="perl">#!/usr/bin/perl |
|||
use strict; # Longest_substrings_without_repeating_characters |
|||
use warnings; |
|||
for my $string ( qw( xyzyabcybdfd xyzyab zzzzz a thisisastringtest ) ) |
|||
{ |
|||
local $_ = $string; |
|||
my @sub; |
|||
length $+ >= $#sub and ++$sub[length $+]{$+} while s/.*(.)(.*\K\1.*)|(.+)//s; |
|||
printf "%20s -> %s\n", $string, join ' ', sort keys %{ pop @sub }; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
xyzyabcybdfd -> cybdf zyabc |
|||
xyzyab -> zyab |
|||
zzzzz -> z |
|||
a -> a |
|||
thisisastringtest -> astring ringtes |
|||
</pre> |
</pre> |
||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
Single pass, maintains a |
Single pass, maintains a start position and a table of seen character positions.<br> |
||
If the current character |
If the current character has occurred after start, move that along, then add any longer/equal length start..i to the result set.<br> |
||
Note that having moved start along we certainly won't be any longer than but may still be ''equal'' to maxlen.<br> |
|||
Should be exponentially faster than collecting all possible substrings and then eliminating those with duplicate characters or too short.<br> |
|||
Should be exponentially faster than collecting all possible substrings and eliminating those with duplicate characters or too short.<br> |
|||
It will however collect duplicates before weeding them out at the end. |
|||
It will however collect duplicates (when long enough) before weeding them out at the end. |
|||
<!--<lang Phix>(phixonline)--> |
|||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
<span style="color: #008080;">function</span> <span style="color: #000000;">longest_substrings</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> |
<span style="color: #008080;">function</span> <span style="color: #000000;">longest_substrings</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> |
||
<span style="color: #000080;font-style:italic;">-- |
<span style="color: #000080;font-style:italic;">-- |
||
-- s can be a normal 8-bit ansi string or a |
-- s can be a normal 8-bit acsii/ansi string or a |
||
-- 32-bit unicode sequence from eg utf8_to_utf32(). |
-- 32-bit unicode sequence from eg utf8_to_utf32(). |
||
-- |
-- It will not complain if given utf-8, but may |
||
-- chop up |
-- chop up multibyte characters inappropriately. |
||
-- s must not contain any 0 or non- |
-- s must not contain any 0 or non-integers. |
||
--</span> |
--</span> |
||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span> |
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span> |
||
<span style="color: #000000;">found</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: # |
<span style="color: #000000;">found</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">256</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (ansi, position)</span> |
||
<span style="color: #004080;">integer</span> <span style="color: #000000;">start</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> |
<span style="color: #004080;">integer</span> <span style="color: #000000;">start</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> |
||
<span style="color: #000000;">maxlen</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
<span style="color: #000000;">maxlen</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
||
<span style="color: #004080;">integer</span> <span style="color: #000000;">si</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #000080;font-style:italic;">-- (deliberate typecheck)</span> |
<span style="color: #004080;">integer</span> <span style="color: #000000;">si</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #000080;font-style:italic;">-- (deliberate typecheck)</span> |
||
<span style="color: #008080;">if</span> <span style="color: #000000;">si</span><span style="color: #0000FF;">></span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">found</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #000080;font-style:italic;">-- ( |
<span style="color: #008080;">if</span> <span style="color: #000000;">si</span><span style="color: #0000FF;">></span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">found</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #000080;font-style:italic;">-- (must be unicode then)</span> |
||
<span style="color: # |
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">si</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">#10FFFF</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (limit size to valid chars)</span> |
||
<span style="color: # |
<span style="color: #000000;">found</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">si</span><span style="color: #0000FF;">-</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">found</span><span style="color: #0000FF;">))</span> |
||
<span style="color: #008080;">else</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">fi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">found</span><span style="color: #0000FF;">[</span><span style="color: #000000;">si</span><span style="color: #0000FF;">]</span> |
|||
<span style="color: #000000;">start</span> <span style="color: #0000FF;"> |
<span style="color: #008080;">if</span> <span style="color: #000000;">fi</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">start</span> <span style="color: #008080;">then</span> <span style="color: #000000;">start</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">fi</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
||
<span style="color: #000000;">found</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ss</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">ss</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">si</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
<span style="color: #000080;font-style:italic;">-- aside: we will not have found anything |
|||
-- longer, but may have trimmed 1 added 1 |
|||
-- and therefore still be === maxlen.</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
||
<span style="color: #000000;">found</span><span style="color: #0000FF;">[</span><span style="color: #000000;">si</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: # |
<span style="color: #000000;">found</span><span style="color: #0000FF;">[</span><span style="color: #000000;">si</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span> |
||
<span style="color: #004080;">integer</span> <span style="color: #000000;">newlen</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">start</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> |
<span style="color: #004080;">integer</span> <span style="color: #000000;">newlen</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">start</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> |
||
<span style="color: #008080;">if</span> <span style="color: #000000;">newlen</span><span style="color: #0000FF;">></span><span style="color: #000000;">maxlen</span> <span style="color: #008080;">then</span> |
<span style="color: #008080;">if</span> <span style="color: #000000;">newlen</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">maxlen</span> <span style="color: #008080;">then</span> |
||
<span style="color: # |
<span style="color: #008080;">if</span> <span style="color: #000000;">newlen</span><span style="color: #0000FF;">></span><span style="color: #000000;">maxlen</span> <span style="color: #008080;">then</span> |
||
<span style="color: #000000;"> |
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> |
||
<span style="color: # |
<span style="color: #000000;">maxlen</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">newlen</span> |
||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">start</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span> |
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">start</span><span style="color: #0000FF;">..</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span> |
||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
||
Line 97: | Line 1,152: | ||
<span style="color: #0000FF;">?</span><span style="color: #000000;">longest_substrings</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"a"</span><span style="color: #0000FF;">)</span> |
<span style="color: #0000FF;">?</span><span style="color: #000000;">longest_substrings</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"a"</span><span style="color: #0000FF;">)</span> |
||
<span style="color: #0000FF;">?</span><span style="color: #000000;">longest_substrings</span><span style="color: #0000FF;">(</span><span style="color: #008000;">""</span><span style="color: #0000FF;">)</span> |
<span style="color: #0000FF;">?</span><span style="color: #000000;">longest_substrings</span><span style="color: #0000FF;">(</span><span style="color: #008000;">""</span><span style="color: #0000FF;">)</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 110: | Line 1,165: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
The following algorithm works but is not terribly efficient for long strings. |
The following algorithm works but is not terribly efficient for long strings. |
||
< |
<syntaxhighlight 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)] |
substr = [s[x:y] for x in range(len(s)) for y in range(x+1, len(s) + 1)] |
||
no_reps = [] |
no_reps = [] |
||
Line 123: | Line 1,178: | ||
for s in ["xyzyabcybdfd", "xyzyab", "zzzzz", "a", "α⊆϶α϶", "", |
for s in ["xyzyabcybdfd", "xyzyab", "zzzzz", "a", "α⊆϶α϶", "", |
||
[1, 2, 3, 4, 1, 2, 5, 6, 1, 7, 8, 1, 0]]: |
[1, 2, 3, 4, 1, 2, 5, 6, 1, 7, 8, 1, 0]]: |
||
print(f"{s} => {longest_substring(s)}")</ |
print(f"{s} => {longest_substring(s)}")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 136: | Line 1,191: | ||
===Python: Some optimisation=== |
===Python: Some optimisation=== |
||
The following algorithm only accrues the longest so far. |
The following algorithm only accrues the longest so far. |
||
< |
<syntaxhighlight lang="python">def longest_substring2(s = "xyzyab"): |
||
max_subs, mx = [], 0 |
max_subs, mx = [], 0 |
||
for x in range(len(s)): |
for x in range(len(s)): |
||
Line 146: | Line 1,201: | ||
else: |
else: |
||
max_subs, mx = [sub], y - x |
max_subs, mx = [sub], y - x |
||
return max_subs</ |
return max_subs</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 157: | Line 1,212: | ||
Not going to bother handling arrays since an array is not a string, and the task description '''specifically''' says 'Given a string'. |
Not going to bother handling arrays since an array is not a string, and the task description '''specifically''' says 'Given a string'. |
||
<lang |
<syntaxhighlight lang="raku" line>sub abbreviate ($_) { .chars > 80 ?? "(abbreviated)\n" ~ .substr(0,35) ~ ' ... ' ~ .substr(*-35) !! $_ } |
||
sub longest ($string) { |
sub longest ($string) { |
||
Line 183: | Line 1,238: | ||
# check a file |
# check a file |
||
slurp 'unixdict.txt';</ |
slurp 'unixdict.txt';</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Original string: xyzyabcybdfd |
<pre>Original string: xyzyabcybdfd |
||
Line 225: | Line 1,280: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
< |
<syntaxhighlight lang="rexx">/*REXX pgm finds the longest substring (in a given string) without a repeating character*/ |
||
parse arg $ /*obtain optional argument from the CL.*/ |
parse arg $ /*obtain optional argument from the CL.*/ |
||
if $=='' | $=="," then $= 'xyzyabcybdfd' /*Not specified? Then use the default.*/ |
if $=='' | $=="," then $= 'xyzyabcybdfd' /*Not specified? Then use the default.*/ |
||
Line 234: | Line 1,289: | ||
x= /*X: the substring, less the 1st char*/ |
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.*/ |
do k=j+1 to L; x= x || substr($, k, 1) /*search for the max length substrings.*/ |
||
if \ |
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? */ |
_= length(x); if _<maxL then iterate /*is length less then the current max? */ |
||
@._= @._ x; maxL= _ /*add this substring to the max list. */ |
@._= @._ x; maxL= _ /*add this substring to the max list. */ |
||
Line 247: | Line 1,302: | ||
OKx: procedure; parse arg y; do r=1 for length(y)-1 /*look for duplicate chars.*/ |
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 |
if pos(substr(y, r, 1), y, r+1)>0 then return 0 |
||
end /*r*/; return 1</ |
end /*r*/; return 1</syntaxhighlight> |
||
{{out|output|text= when using the default input:}} |
{{out|output|text= when using the default input:}} |
||
<pre> |
<pre> |
||
Line 254: | Line 1,309: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
see "working..." + nl |
see "working..." + nl |
||
see "Longest substrings without repeating characters are:" + nl |
see "Longest substrings without repeating characters are:" + nl |
||
Line 305: | Line 1,360: | ||
see "done..." + nl |
see "done..." + nl |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 315: | Line 1,370: | ||
done... |
done... |
||
</pre> |
</pre> |
||
=={{header|VBScript}}== |
|||
<syntaxhighlight lang="vb"> |
|||
function nrls(byval s1) |
|||
dim i,x |
|||
if len(s1)<2 then nlrs=s :exit function |
|||
s=lcase(replace(s1," ","")) |
|||
redim a(127) |
|||
dim ls:ls=len(s) |
|||
start=1 |
|||
so="" |
|||
ml=1 |
|||
a(asc(left(s,1)))=1 |
|||
for i=2 to ls+1 |
|||
if i>ls then |
|||
rep=true |
|||
else |
|||
x=asc(mid(s,i,1)) |
|||
rep=a(x)<>0 |
|||
end if |
|||
if a(x)<>0 then |
|||
if (i-start)>ml then |
|||
so= mid(s,start,i-start) |
|||
ml=(i-start) |
|||
elseif (i-start)=ml then |
|||
so=so & " " & mid(s,start,i-start) |
|||
end if |
|||
xx=a(x) |
|||
for j= 96 to 122: |
|||
if a(j)<=x then a(j)=0 |
|||
next |
|||
start=xx+1 |
|||
end if |
|||
a(x)=i |
|||
next |
|||
nrls=trim(so) |
|||
erase a |
|||
end function |
|||
sub test (f) |
|||
wscript.stdout.writeline "Original: "&f |
|||
wscript.stdout.writeline "Substrings: "&nrls(f)&vbcrlf |
|||
end sub |
|||
test "dabale arroz a la zorra el abad" |
|||
test "The quick brown fox jumps over the lazy dog" |
|||
test "ae" |
|||
test "aa" |
|||
test "abdefghij" |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Original: dabale arroz a la zorra el abad |
|||
Substrings: rozal lazor |
|||
Original: The quick brown fox jumps over the lazy dog |
|||
Substrings: thequickbrownf |
|||
Original: ae |
|||
Substrings: ae |
|||
Original: aa |
|||
Substrings: a a |
|||
Original: abdefghij |
|||
Substrings: abdefghij |
|||
</pre> |
|||
=={{header|V (Vlang)}}== |
|||
{{trans|go}} |
|||
<syntaxhighlight lang="v (vlang)">fn substrings(s string) []string { |
|||
n := s.len |
|||
if n == 0 { |
|||
return [""] |
|||
} |
|||
mut ss := []string{} |
|||
for i in 0..n { |
|||
for le := 1; le <= n-i; le++ { |
|||
ss << s[i..i+le] |
|||
} |
|||
} |
|||
return ss |
|||
} |
|||
fn distinct_runes(chars []rune) []rune { |
|||
mut m := map[rune]bool{} |
|||
for c in chars { |
|||
m[c] = true |
|||
} |
|||
mut l := []rune{} |
|||
for k,_ in m { |
|||
l << k |
|||
} |
|||
return l |
|||
} |
|||
fn distinct_strings(strings []string) []string { |
|||
mut m := map[string]bool{} |
|||
for str in strings { |
|||
m[str] = true |
|||
} |
|||
mut l := []string{} |
|||
for k,_ in m { |
|||
l << k |
|||
} |
|||
return l |
|||
} |
|||
fn main() { |
|||
println("The longest substring(s) of the following without repeating characters are:\n") |
|||
strs := ["xyzyabcybdfd", "xyzyab", "zzzzz", "a", ""] |
|||
for s in strs { |
|||
mut longest := []string{} |
|||
mut longest_len := 0 |
|||
for ss in substrings(s) { |
|||
if distinct_runes(ss.runes()).len == ss.len { |
|||
if ss.len >= longest_len { |
|||
if ss.len > longest_len { |
|||
longest = longest[..0] |
|||
longest_len = ss.len |
|||
} |
|||
longest << ss |
|||
} |
|||
} |
|||
} |
|||
longest = distinct_strings(longest) |
|||
println("String = '$s'") |
|||
println(longest) |
|||
println("Length = ${longest[0].len}\n") |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Same as Wren entry</pre> |
|||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
{{libheader|Wren-seq}} |
{{libheader|Wren-seq}} |
||
< |
<syntaxhighlight lang="wren">import "./seq" for Lst |
||
var substrings = Fn.new { |s| |
var substrings = Fn.new { |s| |
||
Line 331: | Line 1,520: | ||
System.print("The longest substring(s) of the following without repeating characters are:\n") |
System.print("The longest substring(s) of the following without repeating characters are:\n") |
||
var strs = ["xyzyabcybdfd", "xyzyab", "zzzzz", "a", "" |
var strs = ["xyzyabcybdfd", "xyzyab", "zzzzz", "a", ""] |
||
for (s in strs) { |
for (s in strs) { |
||
var longest = [] |
var longest = [] |
||
Line 342: | Line 1,531: | ||
longestLen = ss.count |
longestLen = ss.count |
||
} |
} |
||
longest.add(ss |
longest.add(ss) |
||
} |
} |
||
} |
} |
||
Line 351: | Line 1,540: | ||
System.print(longest) |
System.print(longest) |
||
System.print("Length = %(longest[0].count)\n") |
System.print("Length = %(longest[0].count)\n") |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
Latest revision as of 16:20, 3 May 2024
- Task
Given a string, find the longest substring without any repeating characters.
- Metrics
- Counting
- Word frequency
- Letter frequency
- Jewels and stones
- I before E except after C
- Bioinformatics/base count
- Count occurrences of a substring
- Count how many vowels and consonants occur in a string
- Remove/replace
- XXXX redacted
- Conjugate a Latin verb
- Remove vowels from a string
- String interpolation (included)
- Strip block comments
- Strip comments from a string
- Strip a set of characters from a string
- Strip whitespace from a string -- top and tail
- Strip control codes and extended characters from a string
- Anagrams/Derangements/shuffling
- Word wheel
- ABC problem
- Sattolo cycle
- Knuth shuffle
- Ordered words
- Superpermutation minimisation
- Textonyms (using a phone text pad)
- Anagrams
- Anagrams/Deranged anagrams
- Permutations/Derangements
- Find/Search/Determine
- ABC words
- Odd words
- Word ladder
- Semordnilap
- Word search
- Wordiff (game)
- String matching
- Tea cup rim text
- Alternade words
- Changeable words
- State name puzzle
- String comparison
- Unique characters
- Unique characters in each string
- Extract file extension
- Levenshtein distance
- Palindrome detection
- Common list elements
- Longest common suffix
- Longest common prefix
- Compare a list of strings
- Longest common substring
- Find common directory path
- Words from neighbour ones
- Change e letters to i in words
- Non-continuous subsequences
- Longest common subsequence
- Longest palindromic substrings
- Longest increasing subsequence
- Words containing "the" substring
- Sum of the digits of n is substring of n
- Determine if a string is numeric
- Determine if a string is collapsible
- Determine if a string is squeezable
- Determine if a string has all unique characters
- Determine if a string has all the same characters
- Longest substrings without repeating characters
- Find words which contains all the vowels
- Find words which contains most consonants
- Find words which contains more than 3 vowels
- Find words which first and last three letters are equals
- Find words which odd letters are consonants and even letters are vowels or vice_versa
- Formatting
- Substring
- Rep-string
- Word wrap
- String case
- Align columns
- Literals/String
- Repeat a string
- Brace expansion
- Brace expansion using ranges
- Reverse a string
- Phrase reversals
- Comma quibbling
- Special characters
- String concatenation
- Substring/Top and tail
- Commatizing numbers
- Reverse words in a string
- Suffixation of decimal numbers
- Long literals, with continuations
- Numerical and alphabetical suffixes
- Abbreviations, easy
- Abbreviations, simple
- Abbreviations, automatic
- Song lyrics/poems/Mad Libs/phrases
- Mad Libs
- Magic 8-ball
- 99 Bottles of Beer
- The Name Game (a song)
- The Old lady swallowed a fly
- The Twelve Days of Christmas
- Tokenize
- Text between
- Tokenize a string
- Word break problem
- Tokenize a string with escaping
- Split a character string based on change of character
- Sequences
11l
F longest_substring2(s)
V max_subs = [s[0.<1]] * 0
V mx = 0
L(x) 0 .< s.len
L(y) x + 1 .. s.len
V sub = s[x .< y]
I y - x >= mx & sub.len == Set(Array(sub)).len
I y - x == mx & sub !C max_subs
max_subs.append(sub)
E
max_subs = [sub]
mx = y - x
R max_subs
L(s) [‘xyzyabcybdfd’, ‘xyzyab’, ‘zzzzz’, ‘a’, ‘’]
print(s‘ => ’longest_substring2(s))
V arr = [1, 2, 3, 4, 1, 2, 5, 6, 1, 7, 8, 1, 0]
print(arr‘ => ’longest_substring2(arr))
- 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]]
Action!
BYTE FUNC GetLength(CHAR ARRAY s BYTE start)
BYTE ARRAY tab(256)
BYTE i
CHAR c
Zero(tab,256)
i=start
WHILE i<=s(0)
DO
c=s(i)
tab(c)==+1
IF tab(c)>1 THEN
EXIT
FI
i==+1
OD
RETURN (i-start)
PROC LongestSubstrings(CHAR ARRAY s)
CHAR ARRAY tmp(256)
BYTE count,maxLen,i,len
IF s(0)=0 THEN
RETURN
FI
i=1 maxLen=0
FOR i=1 TO s(0)
DO
len=GetLength(s,i)
IF len>maxLen THEN
maxLen=len
FI
OD
count=0
FOR i=1 TO s(0)
DO
len=GetLength(s,i)
IF len=maxLen THEN
IF count>0 THEN
Print(", ")
FI
SCopyS(tmp,s,i,i+maxlen-1)
PrintF("""%S""",tmp)
count==+1
FI
OD
RETURN
PROC Test(CHAR ARRAY s)
PrintF("Input: ""%S""%E",s)
Print("Result: [")
LongestSubstrings(s)
PrintE("]") PutE()
RETURN
PROC Main()
Test("xyzyabcybdfd")
Test("xyzyab")
Test("zzzzz")
Test("a")
Test("thisisastringtest")
Test("")
RETURN
- Output:
Screenshot from Atari 8-bit computer
Input: "xyzyabcybdfd" Result: ["zyabc", "cybdf"] Input: "xyzyab" Result: ["zyab"] Input: "zzzzz" Result: ["z", "z", "z", "z", "z"] Input: "a" Result: ["a"] Input: "thisisastringtest" Result: ["astring", "ringtes"] Input: "" Result: []
Ada
with Ada.Text_IO;
procedure Longest_Substring is
function Longest (Item : String) return String is
Hist : array (Character) of Natural := (others => 0);
First : Natural := Item'First;
Last : Natural := Item'First - 1;
Longest_First : Natural := Item'First;
Longest_Last : Natural := Item'First - 1;
procedure Adjust is
begin
if Last - First > Longest_Last - Longest_First then
Longest_First := First;
Longest_Last := Last;
end if;
end Adjust;
begin
if Item = "" then
return Item;
end if;
for Index in Item'Range loop
Last := Index;
Hist (Item (Index)) := Hist (Item (Index)) + 1;
if Hist (Item (Index)) = 1 then
Adjust;
else
for A in First .. Index loop
if (for all E of Hist => E <= 1) then
First := A;
Adjust;
exit;
end if;
Hist (Item (A)) := Hist (Item (A)) - 1;
end loop;
end if;
end loop;
return Item (Longest_First .. Longest_Last);
end Longest;
procedure Test (Item : String) is
use Ada.Text_IO;
begin
Put ("original : '"); Put (Item); Put_Line ("'");
Put ("longest : '"); Put (Longest (Item)); Put_Line ("'");
end Test;
begin
Test ("");
Test ("a");
Test ("xyzyabcybdfd");
Test ("thisisastringtest");
Test ("zzzzz");
end Longest_Substring;
- Output:
original : '' longest : '' original : 'a' longest : 'a' original : 'xyzyabcybdfd' longest : 'zyabc' original : 'thisisastringtest' longest : 'astring' original : 'zzzzz' longest : 'z'
APL
lswrc←{
sfx ← ⌽∘,¨,\∘⌽
wrc ← ⊢(/⍨)⍳∘⍴(∧\=)⍳⍨
ls ← ⊢(/⍨)(⌈/=⊢)∘(≢¨)
ls wrc¨ sfx ⍵
}
- Output:
lswrc¨ 'xyzyabcybdfd' 'xyzyab' 'zzzzz' 'a' '' ┌─────────────┬──────┬───────────┬───┬┐ │┌─────┬─────┐│┌────┐│┌─┬─┬─┬─┬─┐│┌─┐││ ││cybdf│zyabc│││zyab│││z│z│z│z│z│││a│││ │└─────┴─────┘│└────┘│└─┴─┴─┴─┴─┘│└─┘││ └─────────────┴──────┴───────────┴───┴┘
Arturo
unrepeatableSubstrings: function [s][
result: [["",0]]
if zero? s -> return []
if one? s -> return @[s]
loop 0..dec size s 'a [
if (a+1) =< dec size s [
loop a..dec size s 'b [
substr: to :string slice s a b
ss: size substr
if and? -> ss >= last maximum result 'x -> last x
-> substr = unique substr [
result: (select result 'x -> ss = last x) ++ @[@[substr, ss]]
]
]
]
]
result: unique map result 'x -> first x
return result
]
loop ["xyzyabcybdfd", "xyzyab", "zzzzz", "a", ""] 'str ->
print [str "=> longest unrepeatable substring:" unrepeatableSubstrings str]
- Output:
xyzyabcybdfd => longest unrepeatable substring: [zyabc cybdf] xyzyab => longest unrepeatable substring: [zyab] zzzzz => longest unrepeatable substring: [z] a => longest unrepeatable substring: [a] => longest unrepeatable substring: []
AutoHotkey
LSWRC(str){
found := [], result := [], maxL := 0
if (StrLen(str) = 1)
result[str] := true
else while (StrLen(str) >= 2){
s := str
while StrLen(s) >= maxL{
if !(s ~= "(.).*\1"){
found[s] := true
maxL := maxL < StrLen(s) ? StrLen(s) : maxL
break
}
s := SubStr(s, 1, StrLen(s)-1) ; trim last chr
}
str := SubStr(str, 2) ; trim 1st chr and try again
}
maxL := 0
for str in found
maxL := maxL < StrLen(str) ? StrLen(str) : maxL
for str in found
if (StrLen(str) = maxL)
result[str] := true
return result
}
Examples:
db =
(
xyzyabcybdfd
xyzyab
zzz
a
)
for i, line in StrSplit(db, "`n", "`r"){
result := "[", i := 0
for str in LSWRC(line)
result .= str ", "
output .= line "`t> " Trim(result, ", ") "]`n"
}
MsgBox % output
return
- Output:
xyzyabcybdfd > [cybdf, zyabc] xyzyab > [zyab] zzz > [z] a > [a]
BCPL
get "libhdr"
// Fills up 'v' with words where w%0 is the start and w%1 is the end
// of each longest substring
let lswrc(s, v) = valof
$( let seen = vec 255
let start = 1 and i = 1 and maxStart = 1 and maxEnd = 1 and n = 0
for i=0 to 255 do i!seen := false
while i <= s%0
$( test (s%i)!seen
while (s%i)!seen
$( (s%start)!seen := false
start := start + 1
$)
or
$( (s%i)!seen := true
if i - start >= maxEnd - maxStart
$( maxStart := start
maxEnd := i
while n>0 & (v+n-1)%1 - (v+n-1)%0 < i-start
do n := n-1
(v+n)%0 := start
(v+n)%1 := i
n := n+1
$)
i := i + 1
$)
$)
resultis n
$)
let substr(s, start, end, buf) = valof
$( buf%0 := end - start + 1
for i = start to end do
buf%(i-start+1) := s%i
resultis buf
$)
let example(s) be
$( let v = vec 32 and b = vec 32
let n = lswrc(s, v)
writef("Original string: '%s'*N", s)
writes("Longest substrings: ")
test n=0 do
writes("<empty>")
or for i = 0 to n-1 do
writef("'%s' ", substr(s, (v+i)%0, (v+i)%1, b))
wrch('*N')
$)
let start() be
$( example("xyzyabcybdfd")
example("xyzyab")
example("zzzzz")
example("a")
example("")
$)
- Output:
Original string: 'xyzyabcybdfd' Longest substrings: 'zyabc' 'cybdf' Original string: 'xyzyab' Longest substrings: 'zyab' Original string: 'zzzzz' Longest substrings: 'z' 'z' 'z' 'z' 'z' Original string: 'a' Longest substrings: 'a' Original string: '' Longest substrings: <empty>
BQN
LongUniq ← ⌈´⊸=∘(≠¨)⊸/ ∧`∘∊⊸/¨∘↓
Alternative:
LongUniq ← ⊢´∘⊔∘(≠¨)⊸⊏ ∊⊸⊐⟜0⊸↑¨∘↓
Test:
LongUniq¨ "a"‿""‿"zzz"‿"xyzyab"‿"xyzyabcybdfd"
- Output:
┌─ · ⟨ "a" ⟩ ⟨ ⟨⟩ ⟩ ⟨ "z" "z" "z" ⟩ ⟨ "zyab" ⟩ ⟨ "zyabc" "cybdf" ⟩ ┘
C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
struct substr {
const char *start;
size_t length;
};
struct substr *lswrc(const char *str) {
size_t length = strlen(str);
struct substr *arr = malloc(sizeof(struct substr) * (length + 1));
if (!arr) return NULL;
size_t start=0, i=0, maxStart=0, maxEnd=0, n=0;
bool used[256] = {false};
for (i=0; i<length; i++) {
while (used[(unsigned char) str[i]])
used[(unsigned char) str[start++]] = false;
used[(unsigned char) str[i]] = true;
if (i-start >= maxEnd-maxStart) {
maxStart = start;
maxEnd = i;
size_t len = maxEnd - maxStart + 1;
while (n>0 && arr[n-1].length < len) n--;
arr[n].start = &str[start];
arr[n].length = len;
n++;
}
}
arr[n].start = NULL;
arr[n].length = 0;
return realloc(arr, sizeof(struct substr) * (n+1));
}
int main() {
char *examples[] = {"xyzyabcybdfd", "xyzyab", "zzzzz", "a", "", NULL};
for (size_t i=0; examples[i]; i++) {
printf("Original string: \"%s\"\n", examples[i]);
printf("Longest substrings: ");
struct substr *ls = lswrc(examples[i]);
for (size_t j=0; ls[j].start; j++)
printf("\"%.*s\" ", (int)ls[j].length, ls[j].start);
printf("\n");
free(ls);
}
return 0;
}
- Output:
Original string: "xyzyabcybdfd" Longest substrings: "zyabc" "cybdf" Original string: "xyzyab" Longest substrings: "zyab" Original string: "zzzzz" Longest substrings: "z" "z" "z" "z" "z" Original string: "a" Longest substrings: "a" Original string: "" Longest substrings:
C++
#include <iostream>
#include <fstream>
#include <set>
#include <sstream>
#include <string>
#include <vector>
std::vector<std::string> longest_substrings_without_repeats(const std::string& str) {
size_t max_length = 0;
std::vector<std::string> result;
size_t length = str.size();
for (size_t offset = 0; offset < length; ++offset) {
std::set<char> characters;
size_t len = 0;
for (; offset + len < length; ++len) {
if (characters.find(str[offset + len]) != characters.end())
break;
characters.insert(str[offset + len]);
}
if (len > max_length) {
result.clear();
max_length = len;
}
if (len == max_length)
result.push_back(str.substr(offset, max_length));
}
return result;
}
void print_strings(const std::vector<std::string>& strings) {
std::cout << "[";
for (size_t i = 0, n = strings.size(); i < n; ++i) {
if (i > 0)
std::cout << ", ";
std::cout << '\'' << strings[i] << '\'';
}
std::cout << "]";
}
void test1() {
for (std::string str : { "xyzyabcybdfd", "xyzyab", "zzzzz", "a", "thisisastringtest", "" }) {
std::cout << "Input: '" << str << "'\nResult: ";
print_strings(longest_substrings_without_repeats(str));
std::cout << "\n\n";
}
}
std::string slurp(std::istream& in) {
std::ostringstream out;
out << in.rdbuf();
return out.str();
}
void test2(const std::string& filename) {
std::ifstream in(filename);
if (!in) {
std::cerr << "Cannot open file '" << filename << "'.\n";
return;
}
std::cout << "Longest substring with no repeats found in '" << filename << "': ";
print_strings(longest_substrings_without_repeats(slurp(in)));
std::cout << "\n";
}
int main() {
test1();
test2("unixdict.txt");
}
- Output:
Input: 'xyzyabcybdfd' Result: ['zyabc', 'cybdf'] Input: 'xyzyab' Result: ['zyab'] Input: 'zzzzz' Result: ['z', 'z', 'z', 'z', 'z'] Input: 'a' Result: ['a'] Input: 'thisisastringtest' Result: ['astring', 'ringtes'] Input: '' Result: [] Longest substring with no repeats found in 'unixdict.txt': ['mbowel disgrunt']
EasyLang
func$[] longstr s$ .
subr maxtest
if len sub$ >= max
if len sub$ > max
max = len sub$
max$[] = [ ]
.
max$[] &= sub$
.
.
s$[] = strchars s$
len empty[] 255
len pos[] 255
pos = 1
while pos <= len s$[]
c = strcode s$[pos]
if pos[c] > 0
maxtest
pos = pos[c] + 1
pos[] = empty[]
sub$ = ""
c = strcode s$[pos]
.
pos[c] = pos
sub$ &= strchar c
pos += 1
.
maxtest
return max$[]
.
for s$ in [ "xyzyabcybdfd" "xyzyab" "zzzzz" "a" "thisisastringtest" "" ]
print longstr s$
.
- Output:
[ "zyabc" "cybdf" ] [ "zyab" ] [ "z" "z" "z" "z" "z" ] [ "a" ] [ "astring" "ringtes" ] [ "" ]
Factor
USING: formatting grouping io kernel math sequences sets ;
: unique-substrings ( seq n -- newseq )
tuck <clumps> [ cardinality = ] with filter ;
: longest-unique-substring ( seq -- newseq )
dup length { } [ 2dup empty? swap 0 > and ]
[ drop 2dup unique-substrings [ 1 - ] dip ] while
2nip [ "" like ] map members ;
: test ( seq -- )
dup longest-unique-substring "%u -> %u\n" printf ;
"Longest substrings without repeating characters:" print
{ "xyzyabcybdfd" "xyzyab" "zzzzz" "a" "" } [ test ] each
- Output:
Longest substrings without repeating characters: "xyzyabcybdfd" -> { "zyabc" "cybdf" } "xyzyab" -> { "zyab" } "zzzzz" -> { "z" } "a" -> { "a" } "" -> { }
FreeBASIC
dim as string example = "antidisestablishmentarianism is a long word and so is flibbertigibbet."
function nrls( t as string ) as string
dim as integer best=0, best_length=-100, i=1, j, k, curr_length
dim as string c
for i = 1 to len(t)+1
curr_length = 0
for j = i+1 to len(t)+1
curr_length += 1
c = mid(t, j, 1)
for k = i to j - 1
if c = mid(t, k, 1) then goto nexti
next k
next j
nexti:
if curr_length > best_length then
best_length = curr_length
best = i
end if
next i
return mid(t, best, best_length)
end function
print ">";nrls(example);"<"
print ">";nrls("My spoon is too big.");"<"
print ">";nrls("Rosetta Code.");"<"
print ">";nrls("AAAAA");"<"
print ">";nrls("abcdefghijklmnopqrstuvwxyz");"<"
print ">";nrls("aaa aeiou uuu");"<"
- Output:
>blishmentar< >My spo< >ta Code.< >A< >abcdefghijklmnopqrstuvwxyz< > aeiou<
FutureBasic
local fn substrings( t as CFStringRef )
int beg, c, f, rpt, max = 0
for beg = 0 to len(t) - 1
rpt = instr( beg+1, t, mid(t, beg, 1), NSCaseInsensitiveSearch )
if rpt < 0 then rpt = len(t)
c = beg + 1
while c < rpt
f = instr(c + 1, t, mid(t, c, 1), NSCaseInsensitiveSearch)
if f < 0 then f = len(t) else if f < rpt then rpt = f
c++
wend
if rpt - beg < max then continue
if rpt - beg > max then max = rpt - beg : mda_clear
mda_add(0) = mid(t, beg, max)
next
print @"\n The string: \"";t;@"\"\n Substring/s: ";
for c = 0 to mda_count(0) -1
print @"\"";mda(c);@"\" ";
next
print
end fn
window 1, @"Longest Substring/s Without Repeated Letters"
fn substrings(@"xyzyabcybdfd")
fn substrings(@"thisisastringtest")
fn substrings(@"My spoon is too big.")
fn substrings(@"Rosetta Code")
fn substrings(@"AaAaA")
fn substrings(@"abcdefghijklmnopqrstuvwxyz")
fn substrings(@"aaa aeiou uuu")
fn substrings(@"abcdABCD")
handleevents
- Output:
File:Longest Substrings without Repeated Letters.png
Go
package main
import "fmt"
func substrings(s string) []string {
n := len(s)
if n == 0 {
return []string{""}
}
var ss []string
for i := 0; i < n; i++ {
for le := 1; le <= n-i; le++ {
ss = append(ss, s[i:i+le])
}
}
return ss
}
func distinctRunes(chars []rune) []rune {
m := make(map[rune]bool)
for _, char := range chars {
m[char] = true
}
var l []rune
for k := range m {
l = append(l, k)
}
return l
}
func distinctStrings(strings []string) []string {
m := make(map[string]bool)
for _, str := range strings {
m[str] = true
}
var l []string
for k := range m {
l = append(l, k)
}
return l
}
func main() {
fmt.Println("The longest substring(s) of the following without repeating characters are:\n")
strs := []string{"xyzyabcybdfd", "xyzyab", "zzzzz", "a", ""}
for _, s := range strs {
var longest []string
longestLen := 0
for _, ss := range substrings(s) {
if len(distinctRunes([]rune(ss))) == len(ss) {
if len(ss) >= longestLen {
if len(ss) > longestLen {
longest = longest[:0]
longestLen = len(ss)
}
longest = append(longest, ss)
}
}
}
longest = distinctStrings(longest)
fmt.Printf("String = '%s'\n", s)
fmt.Println(longest)
fmt.Printf("Length = %d\n\n", len(longest[0]))
}
}
- 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
J
Implementation:
longnorep=: {{
c=. #y
while. ss=. c ]\ y do.
cnt=. #@~."1 ss
if. c e. cnt do. ~.ss#~ c=cnt return. end.
c=. c-1
end.
}}
Examples:
longnorep 'xyzyabcybdfd'
zyabc
cybdf
longnorep 'xyzyab'
zyab
longnorep 'zzzzz'
z
longnorep ''
longnorep 'astring'
astring
longnorep 'thisisastringtest'
astring
ringtes
longnorep 'Thequickbrownfoxjumpsoverthelazydog'
Thequickbrownf
This also works on sequences of numbers (though the character representation of the sequences of numbers may contain repeated characters, the represented numbers will not contain repetitions):
longnorep 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
jq
Adapted from Julia
Works with gojq, the Go implementation of jq
# Use a dictionary for speed in case of very long strings
def alluniquehead:
length as $n
| if $n <= 1 then .
else . as $in
| {ix: -1}
| until(.i or (.ix == $n);
.ix += 1
| $in[.ix:.ix+1] as $x
| if .dict[$x] then .i = .ix
else .dict[$x] = true
end )
| $in[: .ix]
end ;
def maximal_substring_with_distinct_characters:
. as $in
| length as $n
| {i: -1}
| until( .i == $n or .stop;
.i += 1
| if .max and .max > $n - .i then .stop = true
else ($in[.i:] | alluniquehead) as $head
| if ($head|length) > .max
then .ans = $head
| .max = ($head|length)
else .
end
end)
| .ans;
Test Cases
"xyzyabcybdfd",
"xyzyab",
"zzzzz",
"a", "α⊆϶α϶",
""
| "\"\(.)\" => \"\(maximal_substring_with_distinct_characters)\""
- Output:
"xyzyabcybdfd" => "zyabc" "xyzyab" => "zyab" "zzzzz" => "z" "a" => "a" "α⊆϶α϶" => "α⊆϶" "" => ""
Julia
Works on any array, treating a character string as a character array.
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
- 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]]
Miranda
main :: [sys_message]
main = [ Stdout (show test ++ " -> " ++ show (lswrc test) ++ "\n")
| test <- tests]
tests :: [[char]]
tests = ["xyzyabcybdfd", "xyzyab", "zzz", "a"]
lswrc :: [*]->[[*]]
lswrc s = nub [s' | s'<-noreps; #s' = maxlen]
where maxlen = max (map (#) noreps)
noreps = [norep (drop n s) | n<-[0..#s-1]]
norep = reverse . norep' []
norep' mem [] = mem
norep' mem (a:as) = mem, if a $in mem
= norep' (a:mem) as, otherwise
in :: *->[*]->bool
in item [] = False
in item (a:as) = a = item \/ item $in as
nub :: [*]->[*]
nub = reverse . nub' []
where nub' mem [] = mem
nub' mem (a:as) = nub' mem as, if a $in mem
= nub' (a:mem) as, otherwise
- Output:
"xyzyabcybdfd" -> ["zyabc","cybdf"] "xyzyab" -> ["zyab"] "zzz" -> ["z"] "a" -> ["a"]
Modula-2
MODULE LSWRC;
FROM InOut IMPORT WriteString, WriteLn;
FROM Strings IMPORT Length, Copy;
TYPE Range =
RECORD
start, length: CARDINAL;
END;
(* Returns start and length of every longest substring *)
PROCEDURE lswrc(in: ARRAY OF CHAR; VAR out: ARRAY OF Range): CARDINAL;
VAR i, num, start, strlen, len, maxStart, maxEnd: CARDINAL;
used: ARRAY [0..255] OF BOOLEAN;
BEGIN
FOR i := 0 TO 255 DO used[i] := FALSE; END;
strlen := Length(in);
start := 0;
maxStart := 0;
maxEnd := 0;
i := 0;
num := 0;
WHILE i < strlen DO
IF NOT used[ORD(in[i])] THEN
used[ORD(in[i])] := TRUE;
IF (i - start) >= (maxEnd - maxStart) THEN
maxStart := start;
maxEnd := i;
len := (maxEnd - maxStart + 1);
WHILE (num > 0) AND (out[num-1].length < len) DO
DEC(num);
END;
out[num].start := start;
out[num].length := len;
INC(num);
END;
INC(i);
ELSE
WHILE used[ORD(in[i])] DO
used[ORD(in[start])] := FALSE;
INC(start);
END;
END;
END;
RETURN num;
END lswrc;
PROCEDURE Example(s: ARRAY OF CHAR);
VAR buf: ARRAY [0..127] OF CHAR;
ranges: ARRAY [0..127] OF Range;
i, n: CARDINAL;
BEGIN
WriteString("Original string: ");
WriteString(s);
WriteLn();
n := lswrc(s, ranges);
WriteString("Longest substrings: ");
IF n = 0 THEN
WriteString("<empty>");
ELSE
FOR i := 0 TO n-1 DO
Copy(s, ranges[i].start, ranges[i].length, buf);
buf[ranges[i].length] := CHR(0);
WriteString(buf);
WriteString(" ");
END;
END;
WriteLn();
END Example;
BEGIN
Example("xyzyabcybdfd");
Example("xyzyab");
Example("zzzzz");
Example("a");
Example("");
END LSWRC.
- Output:
Original string: xyzyabcybdfd Longest substrings: zyabc cybdf Original string: xyzyab Longest substrings: zyab Original string: zzzzz Longest substrings: z z z z z Original string: a Longest substrings: a Original string: Longest substrings: <empty>
Nim
This version converts strings to sequences of runes.
import sequtils, strutils, unicode
type Runes = seq[Rune]
func longestSubstrings(str: string): seq[string] =
var runes = str.toRunes
var current: Runes
var res: seq[Runes] # Result as a list of Runes.
var maxlen = 0
for c in runes:
let idx = current.find(c)
if idx >= 0:
if current.len > maxlen:
res = @[current]
maxlen = current.len
elif current.len == maxlen and current notin res:
res.add current
current.delete(0, idx)
current.add c
# Process the last current string.
if current.len > maxlen: res = @[current]
elif current.len == maxlen and current notin res: res.add current
result = res.mapIt($it)
for str in ["xyzyabcybdfd", "xyzyab", "zzzzz", "a", "α⊆϶α϶", ""]:
echo '"', str, '"', " → ", longestSubstrings(str)
echo "\nLongest substrings in concatenated list of words from “unixdict.txt”: ",
longestSubstrings(toSeq("unixdict.txt".lines).join())
- Output:
"xyzyabcybdfd" → @["zyabc", "cybdf"] "xyzyab" → @["zyab"] "zzzzz" → @["z"] "a" → @["a"] "α⊆϶α϶" → @["α⊆϶", "⊆϶α"] "" → @[""] Longest substrings in concatenated list of words from “unixdict.txt”: @["mboweldisgrunt"]
Perl
Gets the same answer that raku does when run against unixdict.txt
#!/usr/bin/perl
use strict; # Longest_substrings_without_repeating_characters
use warnings;
for my $string ( qw( xyzyabcybdfd xyzyab zzzzz a thisisastringtest ) )
{
local $_ = $string;
my @sub;
length $+ >= $#sub and ++$sub[length $+]{$+} while s/.*(.)(.*\K\1.*)|(.+)//s;
printf "%20s -> %s\n", $string, join ' ', sort keys %{ pop @sub };
}
- Output:
xyzyabcybdfd -> cybdf zyabc xyzyab -> zyab zzzzz -> z a -> a thisisastringtest -> astring ringtes
Phix
Single pass, maintains a start position and a table of seen character positions.
If the current character has occurred after start, move that along, then add any longer/equal length start..i to the result set.
Note that having moved start along we certainly won't be any longer than but may still be equal to maxlen.
Should be exponentially faster than collecting all possible substrings and eliminating those with duplicate characters or too short.
It will however collect duplicates (when long enough) before weeding them out at the end.
with javascript_semantics function longest_substrings(sequence s) -- -- s can be a normal 8-bit acsii/ansi string or a -- 32-bit unicode sequence from eg utf8_to_utf32(). -- It will not complain if given utf-8, but may -- chop up multibyte characters inappropriately. -- s must not contain any 0 or non-integers. -- sequence res = {}, found = repeat(0,256) -- (ansi, position) integer start = 1, maxlen = 0 for i=1 to length(s) do integer si = s[i] -- (deliberate typecheck) if si>length(found) then -- (must be unicode then) assert(si<=#10FFFF) -- (limit size to valid chars) found &= repeat(0,si-length(found)) else integer fi = found[si] if fi>=start then start = fi+1 end if end if found[si] = i integer newlen = i-start+1 if newlen>=maxlen then if newlen>maxlen then res = {} maxlen = newlen end if res = append(res,s[start..i]) end if end for res = unique(res,"STABLE") return res end function ?longest_substrings("xyzyabcybdfd") ?longest_substrings("xyzyab") ?longest_substrings("zzzzz") ?longest_substrings("a") ?longest_substrings("")
- Output:
{"zyabc","cybdf"} {"zyab"} {"z"} {"a"} {}
A quick test on unixdict.txt yielded the same results as Raku.
Python
The following algorithm works but is not terribly efficient for long strings.
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)}")
- 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]]
Python: Some optimisation
The following algorithm only accrues the longest so far.
def longest_substring2(s = "xyzyab"):
max_subs, mx = [], 0
for x in range(len(s)):
for y in range(x+1, len(s) + 1):
sub = s[x:y]
if y - x >= mx and len(sub) == len(set(sub)):
if y - x == mx and sub not in max_subs:
max_subs.append(sub)
else:
max_subs, mx = [sub], y - x
return max_subs
- Output:
It gives the same output as function longest_substring()
above.
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.
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]
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
- output when using the default input:
longest substrings in xyzyabcybdfd ───► zyabc cybdf
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
- Output:
working... Longest substrings without repeating characters are: Input: xyzyabcybdfd len = 5 : zyabc len = 5 : cybdf done...
VBScript
function nrls(byval s1)
dim i,x
if len(s1)<2 then nlrs=s :exit function
s=lcase(replace(s1," ",""))
redim a(127)
dim ls:ls=len(s)
start=1
so=""
ml=1
a(asc(left(s,1)))=1
for i=2 to ls+1
if i>ls then
rep=true
else
x=asc(mid(s,i,1))
rep=a(x)<>0
end if
if a(x)<>0 then
if (i-start)>ml then
so= mid(s,start,i-start)
ml=(i-start)
elseif (i-start)=ml then
so=so & " " & mid(s,start,i-start)
end if
xx=a(x)
for j= 96 to 122:
if a(j)<=x then a(j)=0
next
start=xx+1
end if
a(x)=i
next
nrls=trim(so)
erase a
end function
sub test (f)
wscript.stdout.writeline "Original: "&f
wscript.stdout.writeline "Substrings: "&nrls(f)&vbcrlf
end sub
test "dabale arroz a la zorra el abad"
test "The quick brown fox jumps over the lazy dog"
test "ae"
test "aa"
test "abdefghij"
- Output:
Original: dabale arroz a la zorra el abad Substrings: rozal lazor Original: The quick brown fox jumps over the lazy dog Substrings: thequickbrownf Original: ae Substrings: ae Original: aa Substrings: a a Original: abdefghij Substrings: abdefghij
V (Vlang)
fn substrings(s string) []string {
n := s.len
if n == 0 {
return [""]
}
mut ss := []string{}
for i in 0..n {
for le := 1; le <= n-i; le++ {
ss << s[i..i+le]
}
}
return ss
}
fn distinct_runes(chars []rune) []rune {
mut m := map[rune]bool{}
for c in chars {
m[c] = true
}
mut l := []rune{}
for k,_ in m {
l << k
}
return l
}
fn distinct_strings(strings []string) []string {
mut m := map[string]bool{}
for str in strings {
m[str] = true
}
mut l := []string{}
for k,_ in m {
l << k
}
return l
}
fn main() {
println("The longest substring(s) of the following without repeating characters are:\n")
strs := ["xyzyabcybdfd", "xyzyab", "zzzzz", "a", ""]
for s in strs {
mut longest := []string{}
mut longest_len := 0
for ss in substrings(s) {
if distinct_runes(ss.runes()).len == ss.len {
if ss.len >= longest_len {
if ss.len > longest_len {
longest = longest[..0]
longest_len = ss.len
}
longest << ss
}
}
}
longest = distinct_strings(longest)
println("String = '$s'")
println(longest)
println("Length = ${longest[0].len}\n")
}
}
- Output:
Same as Wren entry
Wren
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)
}
}
}
longest = Lst.distinct(longest)
System.print("String = '%(s)'")
System.print(longest)
System.print("Length = %(longest[0].count)\n")
}
- 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