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

Question

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
abadac -> 3
abababab -> 2
helloworld -> 5
longest -> 7
nonrepeating -> 7
substring -> 8
herring -> 4
abracadabra -> 4
codegolf -> 6
abczyoxpicdabcde -> 10

(I took these directly from the other challenge)

Answer 1

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

Answer 2

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

Answer 3

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!

Answer 4

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.

Answer 5

Python, 52 bytes

lambda A,b="":max(len(b:=a+b.split(a)[0])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.

Answer 6

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[0])for i in r.findall(r'((.)((?!\2)(.)(?<!\2.*\4.*\4))*)',s,overlapped=1)]))

Answer 7

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)

Answer 8

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

Answer 9

Haskell, 146 bytes

import Data.Array
f=snd.foldl(\(l,m)(i,c)->
 (l//[(b,max(l!b)(l!c))|b<-['a'..'z']]//[(c,i)],
 max m(i-l!c)))(accumArray(+)0('a','z')[],0).zip[1..]

Try it online!