Rosetta Code

Longest substrings without repeating characters: Difference between revisions

Page Discussion

Longest substrings without repeating characters (view source)

Revision as of 16:20, 3 May 2024

10,144 bytes added ,  24 days ago
Added Easylang
No edit summary
(Added Easylang)
 
(18 intermediate revisions by 10 users not shown)
Line 11:
{{trans|Python: Some optimisation}}
 
<langsyntaxhighlight lang="11l">F longest_substring2(s)
V max_subs = [s[0.<1]] * 0
V mx = 0
Line 29:
 
V arr = [1, 2, 3, 4, 1, 2, 5, 6, 1, 7, 8, 1, 0]
print(arr‘ => ’longest_substring2(arr))</langsyntaxhighlight>
 
{{out}}
Line 42:
 
=={{header|Action!}}==
<langsyntaxhighlight Actionlang="action!">BYTE FUNC GetLength(CHAR ARRAY s BYTE start)
BYTE ARRAY tab(256)
BYTE i
Line 106:
Test("thisisastringtest")
Test("")
RETURN</langsyntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Longest_substrings_without_repeating_characters.png Screenshot from Atari 8-bit computer]
Line 128:
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}}==
<langsyntaxhighlight AutoHotkeylang="autohotkey">LSWRC(str){
found := [], result := [], maxL := 0
if (StrLen(str) = 1)
Line 153 ⟶ 277:
result[str] := true
return result
}</langsyntaxhighlight>
Examples:<langsyntaxhighlight AutoHotkeylang="autohotkey">db =
(
xyzyabcybdfd
Line 169 ⟶ 293:
}
MsgBox % output
return</langsyntaxhighlight>
{{out}}
<pre>xyzyabcybdfd > [cybdf, zyabc]
Line 178 ⟶ 302:
 
=={{header|BCPL}}==
<langsyntaxhighlight lang="bcpl">get "libhdr"
 
// Fills up 'v' with words where w%0 is the start and w%1 is the end
Line 236 ⟶ 360:
example("a")
example("")
$)</langsyntaxhighlight>
{{out}}
<pre>Original string: 'xyzyabcybdfd'
Line 248 ⟶ 372:
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}}==
<langsyntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <string.h>
Line 302 ⟶ 437:
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>Original string: "xyzyabcybdfd"
Line 316 ⟶ 451:
 
=={{header|C++}}==
<langsyntaxhighlight lang="cpp">#include <iostream>
#include <fstream>
#include <set>
Line 383 ⟶ 518:
test1();
test2("unixdict.txt");
}</langsyntaxhighlight>
 
{{out}}
Line 407 ⟶ 542:
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}}
<langsyntaxhighlight lang="factor">USING: formatting grouping io kernel math sequences sets ;
 
: unique-substrings ( seq n -- newseq )
Line 425 ⟶ 606:
 
"Longest substrings without repeating characters:" print
{ "xyzyabcybdfd" "xyzyab" "zzzzz" "a" "" } [ test ] each</langsyntaxhighlight>
{{out}}
<pre>
Line 437 ⟶ 618:
 
=={{header|FreeBASIC}}==
<langsyntaxhighlight lang="freebasic">dim as string example = "antidisestablishmentarianism is a long word and so is flibbertigibbet."
 
function nrls( t as string ) as string
Line 467 ⟶ 648:
print ">";nrls("abcdefghijklmnopqrstuvwxyz");"<"
print ">";nrls("aaa aeiou uuu");"<"
</syntaxhighlight>
</lang>
{{out}}<pre>
>blishmentar<
Line 476 ⟶ 657:
> 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}}
<langsyntaxhighlight lang="go">package main
 
import "fmt"
Line 543 ⟶ 763:
fmt.Printf("Length = %d\n\n", len(longest[0]))
}
}</langsyntaxhighlight>
 
{{out}}
Line 569 ⟶ 789:
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}}==
Line 574 ⟶ 829:
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
<langsyntaxhighlight lang="jq"># Use a dictionary for speed in case of very long strings
def alluniquehead:
length as $n
Line 604 ⟶ 859:
end)
| .ans;
</syntaxhighlight>
</lang>
'''Test Cases'''
<langsyntaxhighlight lang="jq">"xyzyabcybdfd",
"xyzyab",
"zzzzz",
Line 612 ⟶ 867:
""
| "\"\(.)\" => \"\(maximal_substring_with_distinct_characters)\""
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 625 ⟶ 880:
=={{header|Julia}}==
Works on any array, treating a character string as a character array.
<langsyntaxhighlight lang="julia">function alluniquehead(arr)
len = length(arr)
if len > 1
Line 649 ⟶ 904:
println("\"$s\" => ", uarray)
end
</langsyntaxhighlight>{{out}}
<pre>
"xyzyabcybdfd" => ["zyabc", "cybdf"]
Line 660 ⟶ 915:
</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}}==
<langsyntaxhighlight lang="modula2">MODULE LSWRC;
FROM InOut IMPORT WriteString, WriteLn;
FROM Strings IMPORT Length, Copy;
Line 737 ⟶ 1,023:
Example("a");
Example("");
END LSWRC.</langsyntaxhighlight>
{{out}}
<pre>Original string: xyzyabcybdfd
Line 752 ⟶ 1,038:
=={{header|Nim}}==
This version converts strings to sequences of runes.
<langsyntaxhighlight Nimlang="nim">import sequtils, strutils, unicode
 
type Runes = seq[Rune]
Line 782 ⟶ 1,068:
 
echo "\nLongest substrings in concatenated list of words from “unixdict.txt”: ",
longestSubstrings(toSeq("unixdict.txt".lines).join())</langsyntaxhighlight>
 
{{out}}
Line 796 ⟶ 1,082:
=={{header|Perl}}==
Gets the same answer that raku does when run against unixdict.txt
<langsyntaxhighlight lang="perl">#!/usr/bin/perl
 
use strict; # Longest_substrings_without_repeating_characters
Line 807 ⟶ 1,093:
length $+ >= $#sub and ++$sub[length $+]{$+} while s/.*(.)(.*\K\1.*)|(.+)//s;
printf "%20s -> %s\n", $string, join ' ', sort keys %{ pop @sub };
}</langsyntaxhighlight>
{{out}}
<pre>
Line 823 ⟶ 1,109:
Should be exponentially faster than collecting all possible substrings and eliminating those with duplicate characters or too short.<br>
It will however collect duplicates (when long enough) before weeding them out at the end.
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
Line 866 ⟶ 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;">""</span><span style="color: #0000FF;">)</span>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 879 ⟶ 1,165:
=={{header|Python}}==
The following algorithm works but is not terribly efficient for long strings.
<langsyntaxhighlight 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 = []
Line 892 ⟶ 1,178:
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)}")</langsyntaxhighlight>
 
{{out}}
Line 905 ⟶ 1,191:
===Python: Some optimisation===
The following algorithm only accrues the longest so far.
<langsyntaxhighlight lang="python">def longest_substring2(s = "xyzyab"):
max_subs, mx = [], 0
for x in range(len(s)):
Line 915 ⟶ 1,201:
else:
max_subs, mx = [sub], y - x
return max_subs</langsyntaxhighlight>
 
{{out}}
Line 926 ⟶ 1,212:
 
Not going to bother handling arrays since an array is not a string, and the task description '''specifically''' says 'Given a string'.
<syntaxhighlight lang="raku" perl6line>sub abbreviate ($_) { .chars > 80 ?? "(abbreviated)\n" ~ .substr(0,35) ~ ' ... ' ~ .substr(*-35) !! $_ }
 
sub longest ($string) {
Line 952 ⟶ 1,238:
 
# check a file
slurp 'unixdict.txt';</langsyntaxhighlight>
{{out}}
<pre>Original string: xyzyabcybdfd
Line 994 ⟶ 1,280:
 
=={{header|REXX}}==
<langsyntaxhighlight 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.*/
Line 1,016 ⟶ 1,302:
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</langsyntaxhighlight>
{{out|output|text=&nbsp; when using the default input:}}
<pre>
Line 1,023 ⟶ 1,309:
 
=={{header|Ring}}==
<langsyntaxhighlight lang="ring">
see "working..." + nl
see "Longest substrings without repeating characters are:" + nl
Line 1,074 ⟶ 1,360:
 
see "done..." + nl
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,085 ⟶ 1,371:
</pre>
 
=={{header|VlangVBScript}}==
<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 {
Line 1,147 ⟶ 1,501:
println("Length = ${longest[0].len}\n")
}
}</langsyntaxhighlight>
{{out}}
<pre>Same as Wren entry</pre>
Line 1,153 ⟶ 1,507:
=={{header|Wren}}==
{{libheader|Wren-seq}}
<langsyntaxhighlight ecmascriptlang="wren">import "./seq" for Lst
 
var substrings = Fn.new { |s|
Line 1,186 ⟶ 1,540:
System.print(longest)
System.print("Length = %(longest[0].count)\n")
}</langsyntaxhighlight>
 
{{out}}
Chkas
2,016

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/312461...364206"