Skip to content

Instantly share code, notes, and snippets.

@Kasahs
Last active August 29, 2015 14:11
Show Gist options
  • Save Kasahs/5e4ab5fcf7403cc93698 to your computer and use it in GitHub Desktop.
Save Kasahs/5e4ab5fcf7403cc93698 to your computer and use it in GitHub Desktop.
longest substring with non repeating chars
def lnrss(s):
"""
Returns the length of longest substring of input string with no repeated letter.
Assumes input string to be in lower case and ignores any other characters.
"""
l = 0
for i in range(len(s)):
for j in range(len(s) - i):
ss = s[j:j+i+1]
if (not has_rep(ss)) and len(ss)>=l:
l = len(ss)
return l
def has_rep(ss):
memo = {chr(k+97):0 for k in range(26)}
for l in list(ss):
try:
memo[l] += 1
if memo[l] >1 :
return True
except KeyError as e:
pass
return False
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment