18
\$\begingroup\$

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 . Shortest answer in bytes for each language wins

Giuseppe
29.3k3 gold badges33 silver badges106 bronze badges
asked May 7, 2020 at 16:12
\$\endgroup\$
6
  • 7
    \$\begingroup\$ I think it would be clearer to say "the longest substring with no character appearing more than once". The "longest non-repeating substring" sounds like it means the longest substring that doesn’t appear elsewhere in the entire string (which would always be the entire string itself!). \$\endgroup\$ Commented May 7, 2020 at 16:24
  • 1
    \$\begingroup\$ @MitchellSpector Thanks, I've updated the first line of the challenge to use that phrasing \$\endgroup\$ Commented May 7, 2020 at 16:28
  • 1
    \$\begingroup\$ @mathjunkie I don't think that's enough, honestly. Throughout the rest of the challenge you still use the misleading wording. Maybe it's just me not paying attention but the wording is saying something and the test cases another thing. \$\endgroup\$ Commented May 8, 2020 at 0:12
  • 2
    \$\begingroup\$ @RGS Hopefully it's clearer now \$\endgroup\$ Commented May 8, 2020 at 0:24
  • 3
    \$\begingroup\$ @mathjunkie it is perfect now; thanks for your time and thanks for the challenge \$\endgroup\$ Commented May 8, 2020 at 0:25

24 Answers 24

8
\$\begingroup\$

Python 3.8 (pre-release), 51 bytes

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

Try it online!

answered May 7, 2020 at 17:07
\$\endgroup\$
0
5
\$\begingroup\$

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
answered May 7, 2020 at 16:25
\$\endgroup\$
4
\$\begingroup\$

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
answered Nov 1, 2022 at 19:00
\$\endgroup\$
9
  • 1
    \$\begingroup\$ Can use .~ instead of length.. Also in->= and collect(z)->[z...]. The answer should get to 83 bytes \$\endgroup\$ Commented Nov 1, 2022 at 20:09
  • 1
    \$\begingroup\$ 80 bytes with also unique->∪ \$\endgroup\$ Commented Nov 2, 2022 at 9:20
  • 1
    \$\begingroup\$ Thanks @amelies for the great suggestions as always! Is there a list of Unicode operators and functions in Julia(∪,∈,÷,etc.)? The docs include the math operators, at least. \$\endgroup\$ Commented Nov 2, 2022 at 13:30
  • 1
    \$\begingroup\$ not that I'm aware of...I usually implement the solution without them and then use ? in the repl to find possible unicode replacements \$\endgroup\$ Commented Nov 2, 2022 at 14:21
  • 2
    \$\begingroup\$ since you're using max, the nested loop can be for x=1:~s,y=1:~s so that the inner one is independent from x declaration. Down to 74 bytes \$\endgroup\$ Commented Nov 2, 2022 at 14:47
3
\$\begingroup\$

Wolfram Language (Mathematica), 49 bytes

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

Try it online!

answered May 7, 2020 at 16:47
\$\endgroup\$
3
\$\begingroup\$

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!

answered May 7, 2020 at 17:13
\$\endgroup\$
2
\$\begingroup\$

Python, 63 bytes

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

Try it online!

answered May 7, 2020 at 16:43
\$\endgroup\$
2
\$\begingroup\$

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!

answered May 7, 2020 at 20:56
\$\endgroup\$
2
\$\begingroup\$

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
answered Jun 24, 2020 at 22:18
\$\endgroup\$
2
\$\begingroup\$

Gaia, 11 bytes

$:u/¦l¦¦_⌉)

Try it online!

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

answered Nov 16, 2020 at 17:32
\$\endgroup\$
2
\$\begingroup\$

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
answered Nov 16, 2020 at 21:28
\$\endgroup\$
2
\$\begingroup\$

Vyxal l, 8 bytes

ǎ' ̈=U;ÞG

Try it Online!

answered Nov 1, 2022 at 17:21
\$\endgroup\$
1
  • \$\begingroup\$ The filter can be replaced with ~Þu for a byte shave \$\endgroup\$ Commented Nov 2, 2022 at 0:01
2
\$\begingroup\$

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
answered Nov 1, 2022 at 23:17
\$\endgroup\$
1
\$\begingroup\$

Japt v2.0a0, 9 bytes 

ã Ôæ_¶âÃl

Try it

answered May 7, 2020 at 17:01
\$\endgroup\$
1
\$\begingroup\$

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.

answered May 7, 2020 at 18:52
\$\endgroup\$
1
\$\begingroup\$

Bash + Core utilities, 46 bytes

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

Try the test cases online!

answered May 7, 2020 at 21:43
\$\endgroup\$
1
\$\begingroup\$

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
answered May 8, 2020 at 1:53
\$\endgroup\$
1
\$\begingroup\$

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.

answered Jun 24, 2020 at 17:32
\$\endgroup\$
1
\$\begingroup\$

Stax, 11 bytes 

éôU)1円⁄4ó8∩╦z

Run and debug it

answered Nov 16, 2020 at 6:35
\$\endgroup\$
1
\$\begingroup\$

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
answered Nov 1, 2022 at 22:29
\$\endgroup\$
1
\$\begingroup\$

Brachylog, 7 bytes

⊇S&sS≠l

Try it online!

Another 7 bytes solution:

sf≠slm⌉

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:

sf Find all substrings of consecutive elements from the input
 ≠s Select all substrings with all-different elements
 lm Map length
 ⌉ Max
answered Nov 2, 2022 at 12:56
\$\endgroup\$
0
\$\begingroup\$

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!

answered May 7, 2020 at 16:41
\$\endgroup\$
0
\$\begingroup\$

Charcoal, 20 bytes

I⌈Eθ⌊Eθ§⌕A+✂θκLθ1λλ1

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
 E Map over characters
 θ Input string
 E Map over characters
 θ Input string
 ✂ κLθ1 Substring starting at outer index
 + λ Append current character
 ⌕A λ Find all matches of the current character
 § 1 Take the second
 ⌊ Take the minimum
 ⌈ Take the maximum
I Cast to string
 Implicitly print
answered May 7, 2020 at 18:45
\$\endgroup\$
0
\$\begingroup\$

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

answered May 9, 2020 at 5:56
\$\endgroup\$
0
\$\begingroup\$

Ohm v2, 16 bytes

l@3ドル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@3ドルsÇ;{??DU=;»l↑
l@ # Push the range [1, len(input)]
 € ; # To each number:
 3sÇ # 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
answered Nov 2, 2022 at 12:42
\$\endgroup\$

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.