Given a string, find the length of the longest substring without repeating characters

Question

I wrote an algorithm that solves this problem but I would love to get some feedback on it (especially since I'm not so confident in my Big \$O\$ skills).

Do you think this is a good quality algorithm? Is it efficient? What would be your impression if you were an interviewer? I really want to improve as a programmer so any help is appreciated!

def lengthOfLongestSubstring(self, word):
    longest =0
    currentLength = 0

    if(len(word) > 0):
        currentLength = 1
        longest = 1
        dict = {word[0] : 0}
        i = 1

        while i < len(word):
            if (dict.has_key(word[i])):
                i = dict[word[i]]+1
                dict.clear()
                if (longest < currentLength):
                    longest= currentLength
                currentLength = 0
            else:
                dict[word[i]] = i
                currentLength = currentLength + 1
                i = i + 1

        if (longest < currentLength):
            longest= currentLength

    return longest

Answer 1

The algorithmic complexity of your solution is \$O(N*C)\$ where \$N\$ is the number of characters in the string and \$C\$ is the size of the alphabet. Assuming lowercase ASCII characters, that's a linear algorithm and will probably be good enough for most things. That being said, it is possible to solve the same problem in \$O(N)\$.

Before that though, your current solution is hard to read. So let's simplify it.

1. If most of your code is inside an if statement, use a guard instead.
2. Don't use generic names like dict for variables. Especially not if the name is already taken. dict is a class in python.
3. You can use in and not in operators instead of has_key. e.g, if key in dictionary:
4. Use functions like max and min instead of conditionals. Actually, just avoid conditionals wherever possible. The more nested your code is, the harder it is to read.

Here's my take on the same program:

def lengthOfLongestSubstring(self, word):
    if not word: return 0

    currentLength = 1
    longest = 1
    lastSeen = {word[0] : 0}
    i = 1

    while i < len(word):
        letter = word[i]
        if letter in last_seen:
            i = last_seen[letter] + 1
            last_seen.clear()
            longest = max(longest, currentLength)
            currentLength = 0
        else:
            last_seen[letter] = i
            currentLength += 1
            i += 1

    longest = max(longest, currentLength)

    return longest

While it's a bit better, I still don't like it. Jumping back and forth is hard to wrap your head around, and it would be nice if the algorithm didn't do that.

Let's try brute force:

def lengthOfLongestSubstring(self, word):
    n = len(word)
    longest = 0
    for i in range(n):
        seen = set()
        for j in range(i, n):
            if word[j] in seen: break
            seen.add(word[j])
        longest = max(len(seen), longest)
    return longest

This one is pretty easy to understand and is still \$O(N * C)\$ in the worst case. Practically this will generally be slower that your solution, but not by that much.

Is there a way to get both readability and speed though? Yep. We don't need to go that far from your idea either. Just a couple minor changes.

Let's think about left most character that you can still include in a replication free substring while going right. Clearly, this character must be to the right of any character that has been seen again. If we know the position of this character than the longest substring ending at the current index is easy to calculate. Here's an implementation:

def lengthOfLongestSubstring(self, word):
    # Initially we can go as far to the left as we want
    left_most_valid = 0
    longest = 0
    last_seen = {}

    for i, letter in enumerate(word):
        if letter in last_seen:
            # left_most_valid must be greater than any position which has been seen again
            left_most_valid = max(left_most_valid, last_seen[letter] + 1)
        last_seen[letter] = i

        # Length of substring from left_most_valid to i is i - left_most_valid + 1
        longest = max(longest, i - left_most_valid + 1)

    return longest

This is an \$O(n)\$ algorithm and about as fast as reading the string from input.