This task have linear time solution:
def solve(s): uniq = set() beg = 0 end = 0 best_beg = 0 best_end = 0 while end < len(s): ch = s[end] if ch in uniq: if best_end - best_beg < end - beg: best_end = end best_beg = beg while s[beg] != ch: uniq.remove(s[beg]) beg += 1 beg += 1 else: uniq.add(ch) end += 1 if best_end - best_beg < end - beg: best_end = end best_beg = beg return s[best_beg:best_end] print(solve("abcd")) print(solve("aba")) print(solve("abcadbef")) print(solve("aaaaa"))
which is based on moving across continuous series of unique characters from the beginning of string.
Compare with solution from http://blog.gainlo.co/index.php/2016/10/07/facebook-interview-longest-substring-without-repeating-characters/
def solution(s): beg = 0 end = 0 longest = '' uniq = set() while end < len(s): end += 1 ch = s[end - 1] if ch not in uniq: uniq.add(ch) if end - beg > len(longest): longest = s[beg:end] continue while beg < end - 1: if s[beg] != ch: uniq.remove(s[beg]) beg += 1 else: beg +=1 break return longest
(which I OCRed with tesseract
and edited since they provide PNG image instead of text for code).
They unnecessary cut longest string with longest = s[beg:end]
each time they expand region.
And have ugly:
while beg < end - 1: if s[beg] != ch: uniq.remove(s[beg]) beg += 1 else: beg +=1 break
with unnecessary check beg < end - 1
because we actually look for condition s[beg] == ch
.
That corresponds to my:
while s[beg] != ch: uniq.remove(s[beg]) beg += 1 beg += 1
so we skip up to duplication character position and move beyond it and it will be before end
by
guarantee of our uniq
set.