Oleksandr Gavenko's blog
2017-01-18 23:00 Longest substring without repeating characters

Another interesting task for interview is "Longest substring without repeating characters".

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.

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

interview, problem ## Feeds

all / emacs / java

## Tags

adb(1), admin(1), android(1), anki(1), ansible(2), blog(2), c(1), css(2), cygwin(2), driver(1), emacs(3), fs(1), git(3), google(1), gradle(1), hardware(1), hg(2), html(1), interview(13), java(3), js(3), lang(2), lighttpd(1), markdown(1), mobile(1), naming(1), oracle(1), print(1), problem(5), python(1), quiz(6), rst(2), security(3), spring(1), sql(2), srs(1), style(1), tls(2), txt(1), unit(1), utils(1), vcs(3), web(2), win(2), windows(1)