LZ77 Triple Encode

Problem

Encode s with greedy LZ77 using a sliding window of the given size. At each position find the longest match against earlier positions within the window; a match may not run past the current position. Break ties toward the nearest match. Emit [offset, length, next_char] and advance past the match plus its next character; when the match reaches the end of the string use an empty string as the character. With no match emit [0, 0, s[i]]. Return the list of triples.

Hint

Compare each candidate match start against the current position and cap the overlap.

Test cases

case 1

in: ["aaaaa",3]

expected: [[0,0,"a"],[1,1,"a"],[2,2,""]]

case 2

in: ["abcabcabc",6]

expected: [[0,0,"a"],[0,0,"b"],[0,0,"c"],[3,3,"a"],[3,2,""]]

case 3

in: ["banana",3]

expected: [[0,0,"b"],[0,0,"a"],[0,0,"n"],[2,2,"a"]]

case 4

in: ["abcd",4]

expected: [[0,0,"a"],[0,0,"b"],[0,0,"c"],[0,0,"d"]]

case 5

in: ["",2]

expected: []

Starter codePython

def lz77_encode(s, window):
    # Your code here
    pass

5 test cases · run your code against them in the editor