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)


9 Answers 9


JavaScript (ES6), 62 bytes

Expects an array of characters.


Try it online!


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
  • \$\begingroup\$ Wow, this must be the most obscure code I have seen in quite some time! \$\endgroup\$
    – anatolyg
    Commented Jan 19, 2023 at 13:10
  • \$\begingroup\$ 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? \$\endgroup\$
    – Jonah
    Commented Jan 19, 2023 at 14:42
  • \$\begingroup\$ @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. \$\endgroup\$
    – Arnauld
    Commented Jan 19, 2023 at 15:09
  • \$\begingroup\$ Oh I get it, it is undefined at first and then you are adding that as a property.... Thanks. \$\endgroup\$
    – Jonah
    Commented Jan 19, 2023 at 15:31

Vyxal, 10 6 bytes


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!

  • \$\begingroup\$ -6 bytes by changing parameter to &[usize] and getting rid of the cast. ATO \$\endgroup\$
    – corvus_192
    Commented Jan 20, 2023 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)[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.


Excel (ms365), 149 bytes

enter image description here

Formula in B1:


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)]))

Nibbles, 10 bytes


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


Try it online!

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


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

Haskell, 146 bytes

import Data.Array
 max m(i-l!c)))(accumArray(+)0('a','z')[],0).zip[1..]

Try it online!


Your Answer

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

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