Length of Longest Non-Repeating Substring

Question

Your task is to take as input a single string (or list of characters, list of code points, etc.) and return the length of the longest substring with no character appearing more than once.

Aside: This challenge is similar to Longest Non-Repeating Substring, but without the source restriction ranking submissions by their own longest non-repeating substring.

---

Assumptions

• You may assume that the input contains only lowercase letters and is non-empty (ie. the input will match the regex (a-z)+).

• This challenge will use the following definition for substring: "A contiguous sequence of characters contained in the input string"

• By "non-repeating" I mean that no letter of the substring is repeated more than once

Examples

If the input is abcdefgabc then the longest substrings with no repeating characters are abcdefg and bcdefga (their positions in the string are [abcdefg]abc and a[bcdefga]bc). The length of these substrings is 7, so the output would be 7.

If the input is abadac then the longest substrings with no repeating characters are bad (a[bad]ac) and dac (aba[dac]) so the output is 3.

If the input is aaaaaa then the longest substring with no repeating characters is a so the output is 1.

If the input is abecdeababcabaa then the longest substrings with no repeating characters are abecd ([abecd]eababcabaa) and cdeab (abe[cdeab]abcabaa). The output is thus 5.

Test Cases

abcdefgabc -> 7
aaaaaa -> 1
abecdeababcabaa -> 5
abadac -> 3
abababab -> 2
helloworld -> 5
longest -> 7
nonrepeating -> 7
substring -> 8
herring -> 4
abracadabra -> 4
codegolf -> 6
abczyoxpicdabcde -> 10

Scoring

This is code-golf. Shortest answer in bytes for each language wins

Answer 1

Python 3.8 (pre-release), 51 bytes

f=lambda s:s>''and max(n:=f(s[:-1]),len({*s[~n:]}))

Try it online!

Answer 2

Jelly, 6 bytes

ẆQƑƇṪL

A monadic link accepting a list of characters (or whatever), which yields the length.

Try it online!

How?

ẆQƑƇṪL - Link: list
Ẇ      - all sublists (ordered by length)
   Ƈ   - filter keep those which are:
  Ƒ    -   invariant under:
 Q     -     deduplication
    Ṫ  - tail
     L - length

Answer 3

Julia 1.0, 98 74 73 bytes

~=length
!s=max(.~filter(z->[z...]==z∪z,[s[x:y] for x=1:~s,y=1:~s])...)

Try it online!

• -3 bytes thanks to @amelies: replace unique with ∪ (union)
• -4 bytes thanks to @amelies: replace collect with splat operator ...
• -6 bytes thanks to @amelies: replace in with = in array comprehension
• -5 bytes thanks to @amelies: vectorize the reassigned operator (~ => .~)
• -2 bytes thanks to @amelies: unary operators don't need parentheses
• -4 bytes thanks to @amelies: condense ranges to remove a for statement
• -1 byte thanks to @MarcMush: replace ∪(z) with z∪z

Answer 4

Wolfram Language (Mathematica), 49 bytes

Tr[1^Last@Select[Subsequences@#,DuplicateFreeQ]]&

Try it online!

Answer 5

C (gcc), 80 bytes

m;f(char*s){int F[128]={},i=0;for(;s[i]*!F[s[i]]++;i++);i=i?i>(m=f(s+1))?i:m:0;}

Try it online!

---

C (gcc), 83 bytes

An alternate non-recursive answer, although 3 bytes longer.

m;f(char*s){for(m=0;*s;)for(char*t=s++,F[128]={};*t*!F[*t]++;m=m>t++-s?m:t-s);++m;}

Try it online!

Answer 6

Python, 63 bytes

f=lambda s:len({*s})<len(s)and max(f(s[1:]),f(s[:-1]))or len(s)

Try it online!

Answer 7

Haskell, 83 75 bytes

-8 using guarded list comprehension for the length.

import Data.List
f[]=0
f x=sum[1|nub x==x,_<-x]`max`f(tail x)`max`f(init x)

Try it online!

Answer 8

R, 88 bytes

function(l)max(apply(combn(seq(l),2),2,function(v)all(table(l[v[1]:v[2]])<2)*diff(v)))+1

Try it online!

Input is vector of individual letters.

Commented:

max(                              # maximum value of:
  apply(                          # loop over
    combn(seq(l),2)               # all pairs of values in 1:length(l)
                                  # (so all possible start & end indices of contiguous subsets)
    ,2,function(v)                # for each pair assigned to 'v':
      all(table(l[v[1]:v[2]])<2)  # table() counts the different items in each subset v[1]:v[2]
                                  # so: 'all(table()<2)' indicates a nonrepeating subset
      *diff(v)                    # multiply by diff(v) = end-start = subset size -1
  ))+1                            # so finally we have to add 1 to get the subset size

Answer 9

Gaia, 11 bytes

$:u/¦l¦¦_⌉)

Try it online!

I feel like there's probably a byte or two that can be removed...

Answer 10

Husk, 8 bytes

▲mLfS=uQ

Try it online!

▲mLfS=uQ
▲           # maximum value of
 mL         # lengths of
   f   Q    # all contiguous sublists of input that are
    S=u     # equal to themselves without duplicates

Answer 11

Vyxal l, 8 bytes

ǎ'¨=U;ÞG

Try it Online!

Answer 12

Pyth, 7 bytes

le{I#.:

Test suite

Explanation:

le{I#.:  | Full code
le{I#.:Q | with implicit variables
---------+-----------------------------------------------------------------------
     .:Q | All substrings of input
    #    | Filter over
  {I     |  whether the substring is the same as itself without duplicate letters
le       | Length of the last (longest) substring

Answer 13

Japt v2.0a0, 9 bytes

ã Ôæ_¶âÃl

Try it

Answer 14

Retina, 28 bytes

Lw`.+
A`(.).*\1
O^$`
$.&
\G.

Try it online! Link includes test cases. Explanation:

Lw`.+

List all nontrivial substrings.

A`(.).*\1

Delete those which duplicate characters.

O^$`
$.&

Sort in descending order of length.

\G.

Count the first length.

The longest length can also be found using these stages for the same byte count:

%C`.

Take the length of each remaining substring.

N^`

Sort in descending order.

1G`

Keep the first length.

Answer 15

Bash + Core utilities, 46 bytes

sed -E ':a;s/(\w)(\w*)\1/\1\2\n\2\1/;ta'|wc -L

Try the test cases online!

Answer 16

05AB1E, 9 bytes

ŒʒDÙQ}€gà

Try it online!

Explanation

Π        All sublists
 ʒ        Filter:
  DÙ      Is the uniquified version
    Q}    Equal to the original?
      €g  Map length
        à Maximum

Answer 17

perl -n -Mfeature=say -MList::Util=max, 55 bytes

m;.+(??{$&=~/(.).*\1/||push@&,length$&})(?!);;say max@&

Try it online!

Reads lines from STDIN, writing results to STDOUT.

For each line, it iterates over every sub string (/.+(?!)/ will do that; /(?!)/ will never match). For each sub string, if it doesn't contain a duplicated character (/(.).*\1/ matches if there is a duplicated character), it stores the length of the sub string. We'll print the maximum of those values.

Answer 18

Stax, 11 bytes

éôU)¥¼ó8∩╦z

Run and debug it

Answer 19

Factor, 48 bytes

[ all-subseqs [ all-unique? ] find-last length ]

Try it online!

• all-subseqs Get all the substrings of the input from shortest to longest
• [ all-unique? ] find-last Find the last one whose elements are unique
• length Get its length

Answer 20

Brachylog, 7 bytes

⊇S&sS≠l

Try it online!

Another 7 bytes solution:

sᶠ≠ˢlᵐ⌉

Try it online!

Explanation

Unfortunately, s - substring does not enumerate substrings of consecutive elements in descending order of length (if it did, we would have a 3 byte solution), but rather enumerates based on the indices. Therefore, we first state that we want a ⊇ - sublist, which does not force consecutiveness, but which enumerates from longest to smallest.

⊇S         S is a subset of the input (from longest to smallest)
  &        And
   sS      S is also a substring of consecutive elements of the input
     ≠     All elements of S are different
      l    Output the length of S

The second solution is a more "declarative" approach:

sᶠ         Find all substrings of consecutive elements from the input
  ≠ˢ       Select all substrings with all-different elements
    lᵐ     Map length
      ⌉    Max

Answer 21

JavaScript (ES6), 72 bytes

f=s=>/(.).*\1/.test(s)?Math.max(f(s.slice(1)),f(s.slice(0,-1))):s.length

Try it online!

---

JavaScript (ES6), 61 bytes

A port of @dingledooper's clever Python answer is 11 bytes shorter.

f=s=>p=s?f(s.slice(1))>(q=new Set(s.slice(0,p+1)).size)?p:q:0

Try it online!

Answer 22

Charcoal, 20 bytes

Ｉ⌈Ｅθ⌊Ｅθ§⌕Ａ⁺✂θκＬθ¹λλ¹

Try it online! Link is to verbose version of code. Works by finding the maximum earliest duplicated character of the string and its nontrivial suffixes. Explanation:

   θ                    Input string
  Ｅ                     Map over characters
      θ                 Input string
     Ｅ                  Map over characters
            θ           Input string
           ✂ κＬθ¹       Substring starting at outer index
          ⁺      λ      Append current character
        ⌕Ａ        λ     Find all matches of the current character
       §           ¹    Take the second
    ⌊                   Take the minimum
 ⌈                      Take the maximum
Ｉ                       Cast to string
                        Implicitly print

Answer 23

T-SQL, 118 bytes

Input is taken from table T (according to the Code Golf rules for SQL): column P represents position and column V represents each character.

SELECT TOP 1B.P-A.P+1FROM T A, T B ORDER BY(SELECT COUNT(*)-COUNT(DISTINCT V)FROM T WHERE T.P>=A.P AND T.P<=B.P),1DESC

DB Fiddle

Answer 24

Ohm v2, 16 bytes

l@€³sÇ;{⁇DU⁼;»l↑

Try it online!

Took me this long to realise » goes before the component. Almost submitted a 17 byte answer using €l;.

Explained

l@€³sÇ;{⁇DU⁼;»l↑
l@                # Push the range [1, len(input)]
  €   ;           # To each number:
   ³sÇ            #   Get all substrings of length number of the input
       {          # Deep flatten that
        ⁇DU⁼;     # And only keep substrings that have all unique characters
             »l   # Push the length of each unique character substring
               ↑  # and get the biggest length