Encode and Decode Strings: Why Length Prefixes Beat Delimiters

"Design an algorithm to encode a list of strings into a single string, and decode it back." The first idea is always a separator, and the interviewer's first reply is always: what if a string contains your separator? The real answer is a technique from network protocols, length-prefix framing, and it fits in two short functions.

The problem it solves

You have a list such as ["hi", "a#b", ""] and a channel that carries exactly one string. Write encode and decode so that decode(encode(parts)) == parts for every list, including:

• strings that contain any character at all, digits and your separator included;
• empty strings;
• the empty list.

The decoder has no side channel. Everything it needs to find the boundaries must be inside the one string.

The intuition

A delimiter reserves a character. ",".join(["hi", "a,b", ""]) gives hi,a,b,, and splitting that returns four parts instead of three. Whatever character you reserve is one the data can no longer contain, and a general-purpose encoder cannot promise that.

There are two ways out:

• Escaping. Keep the delimiter, but write a backslash before every delimiter or backslash inside the data. It works, but the decoder has to inspect every character, and the rules are easy to get subtly wrong.
• Length prefix. Write each part's length first, then a marker, then the part itself: 2#hi3#a#b0#. The decoder reads digits up to the first #, which tells it exactly how many characters follow, and copies them without looking at them. A # inside the payload is just data, because the decoder is never searching for one there.

The marker only has to end the number, and a number is made of digits, so any non-digit works.

Watch it run

The animation encodes two parts, one of which contains a #. It writes the header 2#, copies the payload unexamined, then 3# and the second payload. Decoding reverses it: read digits up to the first #, take exactly that many characters, jump the cursor past them. Nothing is scanned twice, and an empty part would survive as 0#.

The code

The failure first, then the length-prefix codec:

parts = ["hi", "a,b", ""]
joined = ",".join(parts)
print(repr(joined), joined.split(","))       # 'hi,a,b,' ['hi', 'a', 'b', '']

def encode(parts):
    return "".join(f"{len(p)}#{p}" for p in parts)

def decode(s):
    out, i = [], 0
    while i < len(s):
        j = s.index("#", i)                  # digits end at the first # after i
        n = int(s[i:j])
        out.append(s[j + 1:j + 1 + n])       # copy n characters, unexamined
        i = j + 1 + n                        # land on the next header
    return out

wire = encode(["hi", "a#b", "", "12#"])
print(wire)                                  # 2#hi3#a#b0#3#12#
print(decode(wire))                          # ['hi', 'a#b', '', '12#']
print(decode(encode([])), decode(encode([""])))   # [] ['']

Escaping, for comparison. Note that it cannot tell the empty list from a list holding one empty string, since both encode to nothing:

def encode_escaped(parts):
    return ",".join(p.replace("\\", "\\\\").replace(",", "\\,") for p in parts)

def decode_escaped(s):
    out, cur, i = [], [], 0
    while i < len(s):
        if s[i] == "\\":
            cur.append(s[i + 1])             # whatever follows a backslash is data
            i += 2
        elif s[i] == ",":
            out.append("".join(cur))
            cur = []
            i += 1
        else:
            cur.append(s[i])
            i += 1
    out.append("".join(cur))
    return out

print(encode_escaped(["a,b", "c\\"]), decode_escaped(encode_escaped(["a,b", "c\\"])))
# a\,b,c\\ ['a,b', 'c\\']

On the wire, lengths are counted in bytes, not characters. A fixed four-byte header avoids the marker altogether:

import struct

def encode_bytes(parts):
    out = bytearray()
    for p in parts:
        data = p.encode("utf-8")
        out += struct.pack(">I", len(data)) + data   # 4-byte big-endian length
    return bytes(out)

def decode_bytes(b):
    out, i = [], 0
    while i < len(b):
        (n,) = struct.unpack_from(">I", b, i)
        out.append(b[i + 4:i + 4 + n].decode("utf-8"))
        i += 4 + n
    return out

print(len("é€"), len("é€".encode("utf-8")), decode_bytes(encode_bytes(["é€", ""])))   # 2 5 ['é€', '']

All three round-trips on 3,000 random lists drawn from an alphabet full of trouble: #, commas, backslashes, digits, spaces and multi-byte characters:

import random

random.seed(15)
alphabet = "ab#,\\0123é€ "
ok = True
for _ in range(3000):
    parts = ["".join(random.choice(alphabet) for _ in range(random.randint(0, 6)))
             for _ in range(random.randint(0, 5))]
    ok &= decode(encode(parts)) == parts
    ok &= decode_bytes(encode_bytes(parts)) == parts
    if parts:                                # escaping cannot express the empty list
        ok &= decode_escaped(encode_escaped(parts)) == parts
print(ok)                                    # True

The complexity

• Encoding writes each character once plus a header of O(log L) digits for a part of length L: O(total length) time and output size.
• Decoding reads each header once and slices each payload once, jumping over it: O(total length). The s.index("#", i) call only ever scans the digits of the current header.
• Overhead is a few characters per part, compared with escaping, which can double a string made entirely of special characters.
• Joining with "".join matters in Python; building the result with += in a loop can degrade to quadratic time.

Where it goes wrong

• Searching for the marker instead of jumping. Calling split("#") or scanning ahead for the next # reintroduces the delimiter problem the prefix was meant to remove.
• Counting characters, sending bytes. "é€" is 2 characters but 5 UTF-8 bytes. A header must use the same unit the reader counts in.
• Dropping empty strings. A codec that writes nothing for "" cannot restore it; 0# keeps it.
• Trusting the length on real input. A network reader should reject a header larger than the remaining data, or the message size it is willing to allocate.

How to say it in an interview

"Any delimiter can appear inside the data, so I prefix each string with its length and a #. To decode, I read digits up to the next #, parse the length n, take exactly the next n characters without inspecting them, and jump past them. That handles any character and empty strings, and both directions are linear in the total length. On a real wire I'd count bytes, or use a fixed-size binary length header, which is how HTTP's Content-Length lets a parser find the end of a body."

The same "state the size, then the content" idea appears when serialising a binary tree, covered in depth in serialize and deserialize a binary tree.