10
\$\begingroup\$

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)

\$\endgroup\$

9 Answers 9

7
\$\begingroup\$

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
\$\endgroup\$
4
  • \$\begingroup\$ Wow, this must be the most obscure code I have seen in quite some time! \$\endgroup\$
    – anatolyg
    Jan 19 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
    Jan 19 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
    Jan 19 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
    Jan 19 at 15:31
7
\$\begingroup\$

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

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!

\$\endgroup\$
1
  • \$\begingroup\$ -6 bytes by changing parameter to &[usize] and getting rid of the cast. ATO \$\endgroup\$
    – corvus_192
    Jan 20 at 18:29
4
\$\begingroup\$

Charcoal, 43 bytes

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

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.

FS«

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

»Iη

Output the final best run length.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

Excel (ms365), 149 bytes

enter image description here

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

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

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

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!

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