Longest substrings without repeating characters

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

Task

Raku

Detects any character when checking for repeated characters, even multi-byte composite characters, control sequences and whitespace.

Note that there is no requirement that the substrings be unique, only that each has no repeated characters internally. <lang perl6>sub abbreviate ($_) { .chars > 80 ?? "(abbreviated)\n" ~ .substr(0,35) ~ ' ... ' ~ .substr(*-35) !! $_ }

sub longest ($string) {

  return 0 => [] unless $string.chars;
  my ($start, $end, @substr) = 0, 0;
  while ++$end < $string.chars {
      my $sub = $string.substr($start, $end - $start);
      if $sub.contains: my $next = $string.substr: $end, 1 {
          @substr[$end - $start].push: $sub;
          $start += 1 + $sub.index($next);
      }
  }
  @substr[$end - $start].push: $string.substr($start);
  @substr.pairs.tail

}

Standard tests

say "\nOriginal string: {abbreviate $_}\nLongest substring(s) chars: ", .&longest

for flat qww<xyzyabcybdfd xyzyab zzzzz a >,

multibyte Unicode

'👒🎩🎓👩‍👩‍👦‍👦🧢🎓👨‍👧‍👧👒👩‍👩‍👦‍👦🎩🎓👒🧢',

check a file

slurp 'unixdict.txt';</lang>

Output:

Original string: xyzyabcybdfd
Longest substring(s) chars: 5 => [zyabc cybdf]

Original string: xyzyab
Longest substring(s) chars: 4 => [zyab]

Original string: zzzzz
Longest substring(s) chars: 1 => [z z z z z]

Original string: a
Longest substring(s) chars: 1 => [a]

Original string: 
Longest substring(s) chars: 0 => []

Original string: 👒🎩🎓👩‍👩‍👦‍👦🧢🎓👨‍👧‍👧👒👩‍👩‍👦‍👦🎩🎓👒🧢
Longest substring(s) chars: 6 => [🧢🎓👨‍👧‍👧👒👩‍👩‍👦‍👦🎩]

Original string: (abbreviated)
10th
1st
2nd
3rd
4th
5th
6th
7th
8t ... rian
zounds
zucchini
zurich
zygote

Longest substring(s) chars: 15 => [mbowel
disgrunt]

REXX

<lang rexx>/*REXX pgm finds the longest substring (in a given string) without a repeating character*/ parse arg $ /*obtain optional argument from the CL.*/ if $== | $=="," then $= 'xyzyabcybdfd' /*Not specified? Then use the default.*/ L= length($) /*L: the length of the given string.*/ maxL= 0 /*MAXL: max length substring (so far).*/ @.= /*array to hold the max len substrings.*/

    do   j=1  for L;    b= substr($, j, 1)      /*search for max length substrings.    */
    x=                                          /*X:   the substring, less the 1st char*/
       do k=j+1  to L;  x= x || substr($, k, 1) /*search for the max length substrings.*/
       if \okx(x)  then iterate j               /*Are there an replications?  Skip it. */
       ss= b || x                               /*build a possible max length substring*/
       _= length(ss);  if _<maxL  then iterate  /*is length less then the current max? */
       @._= @._  ss;   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  ───►   yzyabc bcybdf

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

   if len(strOK[n]) = 1
      del(strOK,n)
   ok

   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

   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

Output:

working...
Longest substrings without repeating characters are:
Input: xyzyabcybdfd
len = 5 : zyabc
len = 5 : cybdf
done...

Wren

Library: Wren-seq

<lang ecmascript>import "/seq" for Lst

var substrings = Fn.new { |s|

   var n = s.count
   if (n == 0) return [""]
   var ss = []
   for (i in 0...n) {
       for (len in 1..n-i) ss.add(s[i...i+len])
   }
   return ss

}

System.print("The longest substring(s) of the following without repeating characters are:\n") var strs = ["xyzyabcybdfd", "xyzyab", "zzzzz", "a", "", ] for (s in strs) {

   var longest = []
   var longestLen = 0
   for (ss in substrings.call(s)) {
       if (Lst.distinct(ss.toList).count == ss.count) { 
           if (ss.count >= longestLen) {
               if (ss.count > longestLen) {
                   longest.clear()
                   longestLen = ss.count
               }
               longest.add(ss.join())
           }
       }
   }

   longest = Lst.distinct(longest)
   System.print("String = '%(s)'")
   System.print(longest)
   System.print("Length = %(longest[0].count)\n")

}</lang>

Output:

The longest substring(s) of the following without repeating characters are:

String = 'xyzyabcybdfd'
[zyabc, cybdf]
Length = 5

String = 'xyzyab'
[zyab]
Length = 4

String = 'zzzzz'
[z]
Length = 1

String = 'a'
[a]
Length = 1

String = ''
[]
Length = 0