Longest substrings without repeating characters

From Rosetta Code
Longest substrings without repeating characters is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
Task

Given a string,   find the   longest substring   without any repeating characters.


Other tasks related to string operations:
Metrics
Counting
Remove/replace
Anagrams/Derangements/shuffling
Find/Search/Determine
Formatting
Song lyrics/poems/Mad Libs/phrases
Tokenize
Sequences



11l

Translation of: Python: Some optimisation
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

Works with: Dyalog 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

Works with: Factor version 0.99 2021-06-02
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

Translation of: Wren
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: jq

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...

Rust 

use itertools::Itertools;
use std::fs;

fn nonrepeating(s: &str) -> Vec<String> {
    let mut max_subs: Vec<String> = vec![];
    let mut mx = 0_usize;
    for i in 0..s.len() {
        for j in i+1..=s.len() {
            let sub = &s[i..j];
            let subbytes = sub.chars().sorted().dedup();
            if j - i >= mx && sub.len() == subbytes.collect_vec().len() {
                if j - i == mx && !max_subs.contains(&sub.to_string()) {
                    max_subs.push(sub.to_string());
                } else {
                    max_subs = vec![sub.to_string()];
                    mx = j - i;
                }
            }
        }
    }
    return max_subs;
}

fn main() {
    let wordsfile = fs::read_to_string("unixdict.txt").unwrap().to_lowercase();
    let results = wordsfile
        .split_whitespace().map(|w| format!("{} ==> {:?}", w, nonrepeating(w)));
    for s in results {
        println!("{}", s);
    }
}
Output:
10th ==> ["10th"]
1st ==> ["1st"]
2nd ==> ["2nd"]
3rd ==> ["3rd"]
4th ==> ["4th"]
5th ==> ["5th"]
6th ==> ["6th"]
7th ==> ["7th"]
8th ==> ["8th"]
9th ==> ["9th"]
a ==> ["a"]
a&m ==> ["a&m"]
a&p ==> ["a&p"]
a's ==> ["a's"]
aaa ==> ["a"]
aaas ==> ["as"]
aarhus ==> ["arhus"]
aaron ==> ["aron"]
    ... many lines ...
zone ==> ["zone"]
zoo ==> ["zo"]
zoology ==> ["logy"]
zoom ==> ["zo", "om"]
zorn ==> ["zorn"]
zoroaster ==> ["roaste", "oaster"]
zoroastrian ==> ["oastri", "strian"]
zounds ==> ["zounds"]
zucchini ==> ["chin"]
zurich ==> ["zurich"]
zygote ==> ["zygote"]

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)

Translation of: go
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

Library: Wren-seq
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
Retrieved from "https://rosettacode.org/wiki/Longest_substrings_without_repeating_characters?oldid=369339"