13
\$\begingroup\$

Your task is to take as input a single string (or list of characters, list of code points, etc.) and return 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\$
  • 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\$ – Mitchell Spector May 7 at 16:24
  • 1
    \$\begingroup\$ @MitchellSpector Thanks, I've updated the first line of the challenge to use that phrasing \$\endgroup\$ – math junkie May 7 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 at 0:12
  • 1
    \$\begingroup\$ @RGS Hopefully it's clearer now \$\endgroup\$ – math junkie May 8 at 0:24
  • 2
    \$\begingroup\$ @mathjunkie it is perfect now; thanks for your time and thanks for the challenge \$\endgroup\$ – RGS May 8 at 0:25

15 Answers 15

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
| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

Python 3.8 (pre-release), 51 bytes

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

Try it online!

| improve this answer | |
\$\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!

| improve this answer | |
\$\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!

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 49 bytes

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

Try it online!

| improve this answer | |
\$\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!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Japt v2.0a0, 9 bytes

ã Ôæ_¶âÃl

Try it

| improve this answer | |
\$\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.

| improve this answer | |
\$\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!

| improve this answer | |
\$\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
| improve this answer | |
\$\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.

| improve this answer | |
\$\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!

| improve this answer | |
\$\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
| improve this answer | |
\$\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

| improve this answer | |
\$\endgroup\$
0
\$\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
| improve this answer | |
\$\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.