Skip to content
BytePatterns

Encode and Decode Strings: Why Length Prefixes Beat Delimiters

7 min readBytePatternsupdated

Turn a list of strings into one string and back: why any delimiter breaks, how length-prefix framing survives every character, escaping, and binary framing.

To encode and decode strings safely, write each string's length before it, as in 2#hi3#a#b, so the decoder takes exactly that many characters instead of searching for a separator. "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 three framings side by side:

FramingBreaks whenDecode cost
Delimiterthe data contains the delimiterone split on the delimiter
Escaped delimiterempty list meets one empty stringinspects every character
Length prefixheader counts the wrong unitreads header, jumps the payload

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#.

Encode and Decode Strings

Step 1 of 10

Two parts to send — and one of them contains a #. Any separator you reserve is a character the data may not hold.

The same interactive animation as the lesson — step through it with the controls.

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.

Frequently asked questions

How do you encode and decode a list of strings?

Prefix each string with its length and a marker, as in 2#hi3#a#b. To decode, read digits up to the next #, take exactly that many characters without inspecting them, and jump past them. It handles any character and empty strings, and both directions are linear in the total length.

Why not just join the strings with a delimiter?

A delimiter reserves a character the data can no longer contain. Joining ["hi", "a,b", ""] with commas gives hi,a,b,, which splits back into four parts instead of three. Escaping fixes that, but the decoder must inspect every character, and it cannot tell the empty list from a list holding one empty string.

What is length prefix encoding?

Length-prefix framing writes each part's size before the part itself, so the reader knows exactly where it ends without searching for a separator. On a real wire the length is counted in bytes, often as a fixed four-byte binary header, which is how HTTP's Content-Length lets a parser find the end of a body.