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

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}
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

• Welcome to Code Review! What Python version is this written for? – Mast Jul 1 '18 at 8:14

## 1 Answer

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

• 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. – DCS Jul 1 '18 at 17:29