Skip to content

Instantly share code, notes, and snippets.

@pratik7368patil
Created May 30, 2020 14:41
Show Gist options
  • Save pratik7368patil/3c3d29cfacf628f4c87203005450ac39 to your computer and use it in GitHub Desktop.
Save pratik7368patil/3c3d29cfacf628f4c87203005450ac39 to your computer and use it in GitHub Desktop.
Find the length of the longest substring without repeating character
# program to find lenght of longest substring without repeating characters.
def findLongestSubstring(string):
l = len(string)
st = 0 # starting point of current substring.
maxlen = 0 # maximum length of substring
start = 0 # starting index of maximum
d = dict() # dictionary to store last occurrence
d[string[0]] = 0 # store occurrence of first character
for i in range(1, l):
if string[i] not in d: # if character not in dict then add it
d[string[i]] = i
else:
if d[string[i]] >= st:
currlen = i - st
if maxlen < currlen:
maxlen = currlen
start = st
st = d[string[i]] + 1
d[string[i]] = i
if maxlen < i - st:
maxlen = i - st
start = st
print(string[start : start + maxlen])
return len(string[start : start + maxlen]) # insted of returning length
# you can return string
string = "ABACDBFB"
print(findLongestSubstring(string))
# the output will be "ACDBF"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment