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.

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 condtion 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 / python

Tags

admin(1), anki(1), blog(1), css(2), cygwin(2), emacs(3), fs(1), git(2), gradle(1), hg(2), html(1), interview(11), java(2), js(3), lang(2), lighttpd(1), mobile(1), naming(1), oracle(1), print(1), problem(5), quiz(6), rst(1), security(1), sql(2), srs(1), style(1), unit(1), utils(1), vcs(3), web(2), win(2)

Archive