Encode and Decode Strings

Problem

Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings. Implement encode(strs) -> str (Machine 1, sender) and decode(s) -> list[str] (Machine 2, receiver) so that decode(encode(strs)) == strs.

Example 1

Input:  strs = ["Hello", "World"]
Output: ["Hello", "World"]

Example 2

Input:  strs = [""]
Output: [""]

Constraints

• 0 <= len(strs) < 100
• 0 <= len(strs[i]) < 200
• strs[i] contains any possible characters out of 256 valid ASCII characters.

Thinking

Let $N$ = total number of characters in all strings, $m$ = len(strs).

• Naive idea (wrong): join with a separator, "#".join(strs), and split("#"). It breaks as soon as a word contains the separator (["a#b"] → "a#b" → ["a", "b"]), and the problem allows any character, so no separator is safe on its own. It also can’t tell [] from [""].
• Key insight: don’t look inside the words at all. Write each word’s length in front of it: "5#Hello5#World". The decoder reads the length, then jumps over exactly that many characters, so it never matters what they are.
  • The # only marks where the length’s digits end (lengths can have up to 3 digits).
  • The first # after a header’s start is always the real separator, because the header is only digits.
• The decoder needs an index it controls (while i < len(s)), not a for loop, because it must jump a variable distance.
• Edge cases to remember: [] (encodes to ""), [""] (encodes to "0#"), words that contain # or digits ("1#a", "5#"), multi-digit lengths (≥ 10 chars), any ASCII character including \x00.

Solution

Approach A — my version (length + # prefix)

Complexity: Time $O(N)$ · Space $O(N)$. Correct, and the same algorithm as the best practice.

• encode is fine.
• In decode, s.find("#", i) only scans the few header digits, and i jumps over the word, so every character is visited about once.
• if len(s) == 1: return output is dead code: no input encodes to a 1-character string ([] → "", [""] → "0#", ["a"] → "1#a"). It was a patch for an earlier bug.

Unchanged except for the signatures; the commented-out first attempt is left out.

def encode_mine(strs: list[str]) -> str:
    output_list = []
    for word in strs:
        output_list.append(str(len(word)) + "#" + word)
    return "".join(output_list)

def decode_mine(s: str) -> list[str]:
    output = []
    if len(s) == 1:  # dead code: no encoded string has length 1
        return output
    i = 0
    while i < len(s):
        deli = s.find("#", i)
        length = int(s[i:deli])
        output.append(s[deli + 1: deli + 1 + length])
        i = deli + length + 1
    return output

Approach B — length + delimiter prefix ✅ best practice

Complexity: Time $O(N)$ · Space $O(N)$. My version without the special case, with clearer names: start is where the word begins, and the next header begins right after the word ends.

def encode(strs: list[str]) -> str:
    return "".join(f"{len(word)}#{word}" for word in strs)

def decode(s: str) -> list[str]:
    result = []
    i = 0                          # always points at the start of a header
    while i < len(s):
        j = s.find("#", i)         # end of the length digits
        start = j + 1
        end = start + int(s[i:j])
        result.append(s[start:end])
        i = end                    # jump over the word: never read its contents
    return result

Approach C — fixed-width length header (no delimiter)

Complexity: Time $O(N)$ · Space $O(N)$. If every length is written with the same number of digits, the decoder doesn’t need a #: it always reads exactly 3 characters. Lengths are < 200, so 3 digits always fit. Real network protocols use this idea with a fixed-size binary length (e.g. 4 bytes). The catch: you must know the maximum length in advance; Approach B works for any length.

WIDTH = 3  # len(word) < 200 fits in 3 digits

def encode_fixed(strs: list[str]) -> str:
    return "".join(f"{len(word):0{WIDTH}d}{word}" for word in strs)  # 5 -> "005"

def decode_fixed(s: str) -> list[str]:
    result = []
    i = 0
    while i < len(s):
        start = i + WIDTH
        end = start + int(s[i:start])
        result.append(s[start:end])
        i = end
    return result

Scratch / Experiments

Max size: 99 random strings of 199 characters drawn from all 256 ASCII codes. All three are $O(N)$. A and B are about the same (~33 µs). C is ~30% slower here; the likely cost is the nested format spec {len(word):0{WIDTH}d}, which is more work per word than {len(word)}. The whole round trip is tens of microseconds, so choose by correctness and simplicity, not speed.

import random

random.seed(0)
strs = ["".join(chr(random.randrange(256)) for _ in range(199)) for _ in range(99)]

for enc, dec in PAIRS:
    print(enc.__name__, "+", dec.__name__)
    %timeit dec(enc(strs))

Takeaways

• Pattern: to pack variable-length items that can contain anything into one string or byte stream, use length-prefix framing: write the length, then the data, and have the reader jump by the length instead of searching for a separator. (HTTP Content-Length, Redis RESP and protobuf all work this way.) A separator alone only works if you also escape it.
• Mistakes I made:
  • char.isnumeric without (): that’s the method object, which is always truthy. Methods need () to run.
  • Read the length as a single character: lengths can have several digits. Read up to the #.
  • Scanned every character with for … enumerate(s): the loop stopped at #s inside words. You can’t change a for loop’s index; assigning to it is overwritten on the next iteration. To jump, use while with your own index.
  • enumerate(s[i:]) numbers the slice from 0, not from i, so the indexes were off by i. s.find("#", i) searches from i and returns an index in s.
  • Added if len(s) == 1 to patch a symptom: no encoded string has length 1. Fix the cause rather than special-casing one input.
• Related problems: Serialize and Deserialize Binary Tree (#297, same encode/decode design for a tree), String Compression (#443, writing counts into a string), Decode String (#394, parsing a number followed by content), Count and Say (#38, reading runs of digits).