LZW Code Count

Problem

Run the LZW encoder starting from a dictionary containing every single character that appears in the input. Emit the code for the current string whenever adding the next character would create an unknown phrase, and flush one final code at the end. Return the number of codes emitted, and 0 for the empty string.

Hint

A repeated pattern makes the dictionary grow, so fewer codes are needed than there are characters.

Test cases

case 1

in: ["AAA"]

expected: 2

case 2

in: ["ABABABA"]

expected: 4

case 3

in: [""]

expected: 0

case 4

in: ["A"]

expected: 1

case 5

in: ["TOBEORNOTTOBEORTOBEORNOT"]

expected: 16

Starter codePython

def lzw_code_count(s):
    # Your code here
    pass

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