Leetcode longest substring with no duplicates

Question

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        longest = ''
        max_len = 0
        for key,value in enumerate(s):
            if value in longest:
                longest = longest[longest.index(value)+1:] + value
            else:
                longest+=value
            max_len = max(max_len,len(longest))
        return max_len                

Here is my solution for leetcode's "longest-substring-without-repeating-characters question". I don't quite understand why my time complexity is so efficient (99% out of all python submissions). Since strings are immutable in python, assuming a strength of length n, won't my algorithm be $$ 1+2+3+...n-1+n = O(n^2)$$ time? But the optimal solution is on \$O(n)\$ yet the runtime from the testcases says my solution is just as good as the optimal one provided?Am I missing something. Also I am having a hard time proving the space complexity for my solution as well.

Answer 1

The linearity of your approach is due to the fact that your longest could never be longer than the size of the alphabet (otherwise it'd have a duplicate for sure). It means that your code runs at \$O(N * A)\$, where \$N\$ is a length of the string, and \$A\$ is a size of alphabet. Since the latter is a constant, you may safely take it out of the big-O, yielding \$O(N)\$.

The asymptotic constant is still a little bit too large (I don't know what alphabet is used in the test cases, but it is safe to assume at least 26), so there is a room for improvement. You correctly noticed that the immutability of the strings may hurt performance; try to get rid of them. A most obvious approach is to preallocate a list (of the alphabet size), and use it as a circular buffer.

In fact, even that is suboptimal. Try to get rid of the explicit buffer at all (hint: two indices into the original string).

It also may be beneficial to keep a dictionary indexed by letters currently present in the buffer with the values being their corresponding indices. This way you can do a constant time lookup rather than linear search in the buffer. Keep in mind however that such a dictionary may itself be costly; I expect it to improve performance if the alphabet is quite large. Try and profile it.

As for the code, it is simple and clean. Not much to say.

Answer 2

Maybe the code is time efficient because you are lucky. Maybe the code is time efficient because you have good intuitions. This review is about moving toward luck playing less of a role in the performance of your code and/or reaching good intuitive conclusions by a more formal path.

Top Down

The code seems to be written bottom up from loops rather than top down from the specification. That makes it hard to reason about how it solves the problem. Leslie Lamport recommends starting with a specification.

f (arrayOfCharacters: I, alphabet: A) -> positiveInteger: Result
Result = Max(S)
S = Sequence of positiveIntegers (S0,S1...Sk):
    where Sk is the length of the k'th substring of I

This is enough to reason about the best case performance. Let N = I.size. If all the characters in I are the same then there are only N-1 character lookups and:

Result = 1
S.size = I.size

The running time depends on the character of character lookups.

The intution for O(n²)

It is possible to have an input I that takes I.length^2 time to run.

A is the alphabet
I is the input stream of characters
N is the length of I
A has more than N characters.
Each character in I is unique.

In that case the longest substring without repeating characters is I and each character of I has to be compared against every other character.

On the other hand

The alphabet A is bounded. That's what makes it an alphabet and the input I a string. For character C_i in input I, the maximum number of comparisons is the size of the alphabet A. The size of the alphabet is a constant and the worst case runtime is:

Min(N*N, N*A.size)

The worst case is N*A.size when N < A.size. In Big-O notation though N*A.size is O(n) implementing an O(n²) may be better when the A.size is large. For example when A is the set of all possible unicode codepoints (1,114,112) and N is 1000.

Going further

The actual number of assigned unicode codepoints (<300,000) is less than the set of all possible unicode codepoints (1,114,112). Using assigned rather than possible code points might improve speed about 3x.

Similarly, the actual number of unique unicode codepoints when I.length = 1000 is less than 1001. So the worst case for I becomes:

Min(N*N, N*A.size, N*I.unique.size)

I.unique.size is not larger than A.size. But because I.unique.size is of order N the Big-O is O(n²). Again, O(n²) may be better than guaranteed O(n). It will be faster when the cost of determining uniques is less than the cost of scanning the entire alphabet for each substring. Or from a practical standpoint when benchmarks against actual data show it is faster. That's engineering versus computer science. Without actual inputs I and without knowing the alphabet for A we have to go with computer science.

Recursion

The question mentions proofs. Often, proofs are inductive. Because there is a mapping between induction and recursing a list, a recursive procedure may be easier to reason about for a person comfortable with proofs. In particular recursion can be applied to the generation of the list of substring lengths S:

# List(character), List(Int), Substring -> List(Int)
define Loop(I, S, substring)
  # no more input
  if I = []
    return S
  # end of substring
  else if I.first in substring 
    Loop(I.rest,
         S.append(substring.size),
         New substring)
  else
    Loop(I.rest,
    S,
    substring.append(I.first)
end define

This makes the top level call:

# List(character) -> Integer
define maxSubstringLength(I)
  return max(Loop(I.rest, [], New Substring.append(I.first)))
end define

The top level call looks a lot like the top level of the specification and the Loop looks a lot like the interior of the specification. It's somewhat obvious that both run in O(n) time in and of themselves.

Localizing bottlenecks

All of the variation in performance is the implementation of in substring within Loop at:

  # end of substring
  else if I.first in substring

And we are free to implement it whatever way works best for whatever particular combination of data and alphabet we are actually dealing with. For example New Substring might return "" or it might return a bitmap of A.size bits or it might return a balanced tree of 32 width or it might return a key:value store etc. Again, it's software engineering versus computer science.

Review Points

• Reasoning about the problem first may facilitate writing code that is easier to reason about.
• As pointed out the accepted answer, attention to features of the specific problem domain (alphabets) is likely to provide better insights into performance than a generic solution.
• Tweeking performance requires engineering research. The memory requirement for in substring can be reduced at least to A.size bits when the membership test is based on a bitmap. In ASCII that's fifteen bytes. For Unicode it's about 125 kilobytes.
• Is encoding the entire space of Unicode into a bitmap good or bad engineering? 125k sounds like a lot of memory compared to pushing 2-4 byte characters into an array. But 125k will often fit into the cache of the CPU. It is harder to reason about data locality when building arrays of seen characters.
• It might be hard to really engineer a robust solution to a Leetcode problem if the solution needs to be written in twenty minutes.

Aside: {In so far as recursion makes reasoning about the algorithm easier for you, Python may be a suboptimal choice. Iteration is idiomatic Python and recursion not idiomatic Python. Recursion is not idiomatic in Python because Python does not have tail recursion and recursive method calls may crash on large inputs when iterative methods would progress.}