8
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! What Python version is this written for? \$\endgroup\$ – Mast Jul 1 '18 at 8:14
13
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Thank you so much for this great explanation! I really enjoyed it and it makes a lot of sense. I hadn't heard of guards before either, so i'll definitely try to work with those in the future! Thank you so much for taking your time to help me. I honestly appreciate this a lot. \$\endgroup\$ – DCS Jul 1 '18 at 17:29
-2
\$\begingroup\$

I would prefer this solution>>

Time and Space Management Optimised:

    def lengthOfLongestSubstring(self, s: str) -> int:
    curlen = maxlen = 0 # curlen saves the max len of substrings ending with current num
    for i, num in enumerate(s):
        curlen -= s[i-curlen:i].find(num)
        maxlen = max(maxlen, curlen)
    return maxlen
\$\endgroup\$

We are looking for answers that provide insightful observations about the code in the question. Answers that consist of independent solutions with no justification do not constitute a code review, and may be removed.

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.