Skip to content

Instantly share code, notes, and snippets.

@h2rashee
Created October 11, 2017 09:12
Show Gist options
  • Save h2rashee/4a144f75cb309f8a30ddbec3059efa8d to your computer and use it in GitHub Desktop.
Save h2rashee/4a144f75cb309f8a30ddbec3059efa8d to your computer and use it in GitHub Desktop.
Given a string, determine the length of the longest substring with no repeating characters
def find_len_substr(string):
start = 0
cur = start
cur_max = 0
seen = {}
while start < len(string):
deja_vu = False
for x in range(start, len(string)):
if string[x] in seen and seen[string[x]] >= start:
# Log upto the spot we have now
length = x - start
if length > cur_max:
cur_max = length
# Move the start pointer up one and keep calculating
start = seen[string[x]] + 1
# Flag variable we'll need once we exit
deja_vu = True
# Short circuit if we can't find a longer substring
if len(string) - start < cur_max:
return cur_max
seen[string[x]] = x
if not deja_vu:
return len(string) - start
return cur_max
assert find_len_substr('abc') == 3
assert find_len_substr('abab') == 2
assert find_len_substr('aaaaabbbbc') == 2
assert find_len_substr('abcbadda') == 4
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment