Longest substrings without repeating characters
- 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
<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))</lang>
- Output:
xyzyabcybdfd => [zyabc, cybdf] xyzyab => [zyab] zzzzz => [z] a => [a] => [] [1, 2, 3, 4, 1, 2, 5, 6, 1, 7, 8, 1, 0] => [[3, 4, 1, 2, 5, 6], [2, 5, 6, 1, 7, 8]]
AutoHotkey
<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 }</lang> Examples:<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</lang>
- Output:
xyzyabcybdfd > [cybdf, zyabc] xyzyab > [zyab] zzz > [z] a > [a]
BCPL
<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("")
$)</lang>
- 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>
C++
<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");
}</lang>
- 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']
Factor
<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</lang>
- Output:
Longest substrings without repeating characters: "xyzyabcybdfd" -> { "zyabc" "cybdf" } "xyzyab" -> { "zyab" } "zzzzz" -> { "z" } "a" -> { "a" } "" -> { }
Go
<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])) }
}</lang>
- Output:
The longest substring(s) of the following without repeating characters are: String = 'xyzyabcybdfd' [zyabc cybdf] Length = 5 String = 'xyzyab' [zyab] Length = 4 String = 'zzzzz' [z] Length = 1 String = 'a' [a] Length = 1 String = '' [] Length = 0
jq
Adapted from Julia
Works with gojq, the Go implementation of jq <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;
</lang> Test Cases <lang jq>"xyzyabcybdfd", "xyzyab", "zzzzz", "a", "α⊆϶α϶", "" | "\"\(.)\" => \"\(maximal_substring_with_distinct_characters)\"" </lang>
- Output:
"xyzyabcybdfd" => "zyabc" "xyzyab" => "zyab" "zzzzz" => "z" "a" => "a" "α⊆϶α϶" => "α⊆϶" "" => ""
Julia
Works on any array, treating a character string as a character array. <lang julia>function alluniquehead(arr)
len = length(arr) if len > 1 for i in 2:len if arr[i] in @view arr[1:i-1] return arr[1:i-1] end end end return arr[:]
end
function maxuniques(arr)
length(arr) < 2 && return arr amax = [alluniquehead(@view arr[i:end]) for i in 1:length(arr)] maxlen = maximum(map(length, amax)) return filter(a -> length(a) == maxlen, amax)
end
for s in ["xyzyabcybdfd", "xyzyab", "zzzzz", "a", "α⊆϶α϶", "", [1, 2, 3, 4, 1, 2, 5, 6, 1, 7, 8, 1, 0]]
uarray = maxuniques(collect(s)) !isempty(uarray) && length(uarray[1]) > 1 && uarray[1][1] isa Char && (uarray = String.(uarray)) println("\"$s\" => ", uarray)
end
</lang>
- Output:
"xyzyabcybdfd" => ["zyabc", "cybdf"] "xyzyab" => ["zyab"] "zzzzz" => [['z'], ['z'], ['z'], ['z'], ['z']] "a" => ['a'] "α⊆϶α϶" => ["α⊆϶", "⊆϶α"] "" => Char[] "[1, 2, 3, 4, 1, 2, 5, 6, 1, 7, 8, 1, 0]" => [[3, 4, 1, 2, 5, 6], [2, 5, 6, 1, 7, 8]]
Modula-2
<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.</lang>
- 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. <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())</lang>
- 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 <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 }; }</lang>
- 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. <lang python>def longest_substring(s = "xyzyab"):
substr = [s[x:y] for x in range(len(s)) for y in range(x+1, len(s) + 1)] no_reps = [] for sub in substr: if len(sub) == len(set(sub)) and sub not in no_reps: no_reps.append(sub) max_len = max(len(sub) for sub in no_reps) if no_reps else 0 max_subs = [sub for sub in no_reps if len(sub) == max_len] return max_subs
if __name__ == '__main__':
for s in ["xyzyabcybdfd", "xyzyab", "zzzzz", "a", "α⊆϶α϶", "", [1, 2, 3, 4, 1, 2, 5, 6, 1, 7, 8, 1, 0]]: print(f"{s} => {longest_substring(s)}")</lang>
- Output:
xyzyabcybdfd => ['zyabc', 'cybdf'] xyzyab => ['zyab'] zzzzz => ['z'] a => ['a'] α⊆϶α϶ => ['α⊆϶', '⊆϶α'] => [] [1, 2, 3, 4, 1, 2, 5, 6, 1, 7, 8, 1, 0] => [[3, 4, 1, 2, 5, 6], [2, 5, 6, 1, 7, 8]]
Python: Some optimisation
The following algorithm only accrues the longest so far. <lang python>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</lang>
- 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'. <lang perl6>sub abbreviate ($_) { .chars > 80 ?? "(abbreviated)\n" ~ .substr(0,35) ~ ' ... ' ~ .substr(*-35) !! $_ }
sub longest ($string) {
return 0 => [] unless $string.chars; my ($start, $end, @substr) = 0, 0; while ++$end < $string.chars { my $sub = $string.substr($start, $end - $start); if $sub.contains: my $next = $string.substr: $end, 1 { @substr[$end - $start].push($sub) 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';</lang>
- Output:
Original string: xyzyabcybdfd Longest substring(s) chars: 5 => [zyabc cybdf] Original string: xyzyab Longest substring(s) chars: 4 => [zyab] Original string: zzzzz Longest substring(s) chars: 1 => [z z z z z] Original string: a Longest substring(s) chars: 1 => [a] Original string: Longest substring(s) chars: 0 => [] Original string: 👒🎩🎓👩👩👦👦🧢🎓👨👧👧👒👩👩👦👦🎩🎓👒🧢 Longest substring(s) chars: 6 => [🧢🎓👨👧👧👒👩👩👦👦🎩] Original string: α⊆϶α϶ 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
<lang rexx>/*REXX pgm finds the longest substring (in a given string) without a repeating character*/ parse arg $ /*obtain optional argument from the CL.*/ if $== | $=="," then $= 'xyzyabcybdfd' /*Not specified? Then use the default.*/ L= length($) /*L: the length of the given string.*/ maxL= 0 /*MAXL: max length substring (so far).*/ @.= /*array to hold the max len substrings.*/
do j=1 for L; b= substr($, j, 1) /*search for max length substrings. */ x= /*X: the substring, less the 1st char*/ do k=j+1 to L; x= x || substr($, k, 1) /*search for the max length substrings.*/ if \OKx(x) then iterate j /*Are there an replications? Skip it. */ _= length(x); if _<maxL then iterate /*is length less then the current max? */ @._= @._ x; maxL= _ /*add this substring to the max list. */ end /*k*/ end /*j*/
say 'longest substring's(words(@.maxL)) "in " $ ' ───► ' @.maxL exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ s: if arg(1)==1 then return arg(3); return word(arg(2) 's', 1) /*simple pluralizer*/ /*──────────────────────────────────────────────────────────────────────────────────────*/ OKx: procedure; parse arg y; do r=1 for length(y)-1 /*look for duplicate chars.*/
if pos(substr(y, r, 1), y, r+1)>0 then return 0 end /*r*/; return 1</lang>
- output when using the default input:
longest substrings in xyzyabcybdfd ───► zyabc cybdf
Ring
<lang ring> see "working..." + nl see "Longest substrings without repeating characters are:" + nl str = "xyzyabcybdfd" see "Input: " + str + nl lenStr = len(str) strOk = [] lenOk = 0
for n = 1 to lenStr
for m = 1 to lenStr-n+1 temp = substr(str,n,m) add(strOk,temp) next
next
for n = len(strOk) to 1 step -1
if len(strOK[n]) = 1 del(strOK,n) ok
next
for n = 1 to len(strOK)
for m = 1 to len(strOK)-1 if len(strOK[m+1]) > len(strOK[m]) temp = strOK[m] strOK[m] = strOK[m+1] strOK[m+1] = temp ok next
next
for n = 1 to len(strOK)
flag = 1 for m = 1 to len(strOK[n]) for p = m+1 to len(strOK[n]) if strOK[n][m] = strOK[n][p] flag = 0 exit ok next next if flag = 1 if len(strOK[n]) >= lenOk see "len = " + len(strOK[n]) + " : " + strOK[n] + nl lenOK = len(strOK[n]) ok ok
next
see "done..." + nl </lang>
- Output:
working... Longest substrings without repeating characters are: Input: xyzyabcybdfd len = 5 : zyabc len = 5 : cybdf done...
Wren
<lang ecmascript>import "/seq" for Lst
var substrings = Fn.new { |s|
var n = s.count if (n == 0) return [""] var ss = [] for (i in 0...n) { for (len in 1..n-i) ss.add(s[i...i+len]) } return ss
}
System.print("The longest substring(s) of the following without repeating characters are:\n") var strs = ["xyzyabcybdfd", "xyzyab", "zzzzz", "a", ""] for (s in strs) {
var longest = [] var longestLen = 0 for (ss in substrings.call(s)) { if (Lst.distinct(ss.toList).count == ss.count) { if (ss.count >= longestLen) { if (ss.count > longestLen) { longest.clear() longestLen = ss.count } longest.add(ss) } } }
longest = Lst.distinct(longest) System.print("String = '%(s)'") System.print(longest) System.print("Length = %(longest[0].count)\n")
}</lang>
- Output:
The longest substring(s) of the following without repeating characters are: String = 'xyzyabcybdfd' [zyabc, cybdf] Length = 5 String = 'xyzyab' [zyab] Length = 4 String = 'zzzzz' [z] Length = 1 String = 'a' [a] Length = 1 String = '' [] Length = 0