# Find the length of the longest substring with all different characters in O(n) time

Let's solve the same task as in this challenge but faster!

Input: a non-empty string containing letters a-z

Output: the length of a longest (contiguous) substring in which all letters are different

Time and space complexity: O(n).

The number of letters in the alphabet is 26, or O(1). Make sure you understand how your language works - e.g. if it can't "extract a substring" in O(1) time, you probably can't use substrings in your implementation - use indices instead.

The solution doesn't need to say at which position it found the longest substring, and whether there is more than one. So, for example, if it found a substring of length 26, it can stop searching (this observation will not help you write your implementation).

### Test Cases

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


(I took these directly from the other challenge)

# JavaScript (ES6), 62 bytes

Expects an array of characters.

a=>a.map((c,i)=>a[m=(d=i-a[c],d<++j?j=d:j)<m?m:j,c]=i,j=m=0)|m


Try it online!

### Commented

a =>                // a[] = input array, reused as an object to keep
// track of the last position of each character
a.map((c, i) =>     // for each character c at position i in a[]:
a[                //
m = (           //   m is the maximum length of a valid substring
d = i - a[c], //   let d be the difference between the current
//   position and the last position of c (NaN if
//   c has not been seen so far)
d < ++j ?     //   increment j; if d is less than j:
j = d       //     we have to force j to d
:             //   else:
j           //     keep the incremented value of j
) < m ?         //   if j is less than m:
m             //     leave m unchanged
:               //   else:
j,            //     update m to j
c               //   update a[c] ...
] = i,            //   ... to i
j = m = 0         //   start with j = m = 0
) | m               // end of map(); return m

• Wow, this must be the most obscure code I have seen in quite some time! Jan 19 at 13:10
• d = i - a[c] -- Maybe I misunderstand your explanation, but c is one of the characters of the array, so how are we indexing into the array with c? Jan 19 at 14:42
• @Jonah Any array is also an object in JS. So a['foo'] is referencing the foo property of the underlying object of the array a. Jan 19 at 15:09
• Oh I get it, it is undefined at first and then you are adding that as a property.... Thanks. Jan 19 at 15:31

# Vyxal, 10 6 bytes

UÞx↔tL


Try it Online!

Shorter than the Vyxal answer in the original challenge. $$\O(nk!)\$$ where $$\n\$$ is the length of the string and $$\k\$$ is the number of unique characters so it times out when $$\k\geq 10\$$.

U      # uniquify
Þx    # combinations without replacement
↔   # keep only those that are in input
t  # tail
L # length


# Rust, 129 127 bytes

|s:&[u8]|{let(mut a,mut d,mut e)=(-1,[-1;128],0);for(i,j)in(0..).zip(s){let f=*j as usize;a=a.max(d[f]);d[f]=i;e=e.max(i-a)}e};


Attempt This Online!

• -6 bytes by changing parameter to &[usize] and getting rid of the cast. ATO Jan 20 at 18:29

# Charcoal, 43 bytes

≔⦃⦄θ≔⁰η≔⁰ζＦＳ«→≔⌊⟦⊕ζ⁻ⅈ∨§θι⁰⟧ζ§≔θιⅈ¿›ζη≔ζη»Ｉη


Attempt This Online! Link is to verbose version of code. Explanation:

≔⦃⦄θ≔⁰η≔⁰ζ


Start with an empty dictionary of previous indices, and zero best and current run length.

ＦＳ«


Loop over the input string.

→


Increment the canvas X coordinate. This keeps track of the current index without using another variable.

≔⌊⟦⊕ζ⁻ⅈ∨§θι⁰⟧ζ


Try to increment the current run length, but reduce it to the difference of the current index with the previous index of the current character (or 0 if the character has not been seen previously).

§≔θιⅈ


Update the last seen index of the current character.

¿›ζη≔ζη


Update the best run length. (≔⌈⟦ηζ⟧η also works for the same byte count.)

»Ｉη


Output the final best run length.

# Python, 52 bytes

lambda A,b="":max(len(b:=a+b.split(a))for a in A)


Storing b back-to-front saves a byte.

Attempt This Online!

### Original Python, 53 bytes

lambda A,b="":max(len(b:=b.split(a)[-1]+a)for a in A)


Attempt This Online!

I'm not sure there are many methods that are not O(n). This one is

### O(n) because

Main loop is over the input string (~> n iterations). Body takes linear time in the length of b which never exceeds the (fixed) size of the alphabet (~> O(1)).

Taken together that gives linear time (in n); taking the max does not change this.

# Excel (ms365), 149 bytes Formula in B1:

=LET(x,SEQUENCE(LEN(A1)),MAX(MAP(REDUCE(0,x,LAMBDA(y,z,VSTACK(y,MID(A1,z,x)))),LAMBDA(q,(LEN(q)=COUNTA(UNIQUE(MID(q,SEQUENCE(LEN(q)),1))))*LEN(q)))))


Thought I'd also chuck in a Python solution though I'm sure someone more proficient with Python will post something much smoother:

from itertools import combinations
s = 'abcdefgabc'
print(max([(len(set(z))==len(z))*len(z)for z in[s[x:y]for x,y in combinations(range(len(s)+1),r=2)]]))


Or, with regular expressions:

import regex as r
s = 'abczyoxpicdabcde'
print(max([len(i)for i in r.findall(r'((.)((?!\2)(.)(?<!\2.*\4.*\4))*)',s,overlapped=1)]))


# Nibbles, 10 bytes

/@~0""]@,;:$/%_$$ Attempt This Online! Time complexity: $$\\mathcal O(nr)\$$, where $$\r\$$ is the result. / Right fold @ each line of input ~ 0 "" with a starting value of (0, "") (ch, accumulator) => ( ] max @ accumulator.first , length of ; s := : join$            ch
/            fold
%            split
_              accumulator.second
$by ch$             first
, s)


# Pyth, 12 bytes

e.MZml=+eckd


Try it online!

Port of @loopy walt's answer. Could replace .MZ with S but that would technically make it $$\O(n\log(n))\$$.

### Explanation

e.MZml=+eckddQ    # implicitly add dQ to the end of the program
# implicitly assign Q = eval(input())
m        Q    # map the letters of Q to lambda d
=+eckdd     #   k = k.split(d)[-1] + d
l            #   length(k)
e.MZ              # get the maximum


import Data.Array