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

\$\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\$ May 7, 2020 at 16:24
  • 1
    \$\begingroup\$ @MitchellSpector Thanks, I've updated the first line of the challenge to use that phrasing \$\endgroup\$ 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\$
    – RGS
    May 8, 2020 at 0:12
  • 2
    \$\begingroup\$ @RGS Hopefully it's clearer now \$\endgroup\$ May 8, 2020 at 0:24
  • 3
    \$\begingroup\$ @mathjunkie it is perfect now; thanks for your time and thanks for the challenge \$\endgroup\$
    – RGS
    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!

\$\endgroup\$
1
  • \$\begingroup\$ @12944qwerty No unfortunately, since I'm calling it recursively. \$\endgroup\$ Nov 9, 2022 at 18:03
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
\$\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
\$\endgroup\$
9
  • 1
    \$\begingroup\$ Can use .~ instead of length.. Also in->= and collect(z)->[z…]. The answer should get to 83 bytes \$\endgroup\$
    – amelies
    Nov 1, 2022 at 20:09
  • 1
    \$\begingroup\$ 80 bytes with also unique-> \$\endgroup\$
    – amelies
    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\$ 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\$
    – amelies
    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\$
    – amelies
    Nov 2, 2022 at 14:47
3
\$\begingroup\$

Wolfram Language (Mathematica), 49 bytes

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

Try it online!

\$\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!

\$\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!

\$\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!

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

\$\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
\$\endgroup\$
2
\$\begingroup\$

Vyxal l, 8 bytes

ǎ'¨=U;ÞG

Try it Online!

\$\endgroup\$
1
  • \$\begingroup\$ The filter can be replaced with ~Þu for a byte shave \$\endgroup\$
    – lyxal
    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
\$\endgroup\$
1
\$\begingroup\$

Japt v2.0a0, 9 bytes

ã Ôæ_¶âÃl

Try it

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

\$\endgroup\$
1
\$\begingroup\$

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!

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

\$\endgroup\$
1
\$\begingroup\$

Stax, 11 bytes

éôU)¥¼ó8∩╦z

Run and debug it

\$\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
\$\endgroup\$
1
\$\begingroup\$

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
\$\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!

\$\endgroup\$
0
\$\begingroup\$

Charcoal, 20 bytes

I⌈Eθ⌊Eθ§⌕A⁺✂θκLθ¹λλ¹

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θ¹       Substring starting at outer index
          ⁺      λ      Append current character
        ⌕A        λ     Find all matches of the current character
       §           ¹    Take the second
    ⌊                   Take the minimum
 ⌈                      Take the maximum
I                       Cast to string
                        Implicitly print
\$\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

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.