Pattern 5: Encoding and design

Not every string problem is about searching for a pattern — some are about representing data. How do you turn a list of strings into a single string and then recover it exactly? The answer teaches a principle that goes well beyond strings.

Tried it? The first idea is almost always to join with a separator (comma, #) — and it breaks the moment a piece of data contains that separator (see the "a#2#b" case). The theory below shows why separators are ambiguous and what the robust solution is.

The theory: the ambiguity problem

I want to join ["abc", "de"] into a single string to transmit, then split it back apart. The naive idea: join with a comma → "abc,de". Seems to work... until one of the pieces contains the separator:

["a,b", "c"]  →  "a,b,c"  →  splitting on ","  →  ["a", "b", "c"]  ✗

We recover 3 strings instead of 2. Any separator you choose can appear in the data — that's the fundamental problem with delimiters. Swapping the comma for another character just kicks the can down the road: what if the data contains that character too?

The solution: length as a prefix (length-prefix)

Instead of marking where each piece ends (a separator, which can collide), mark how long each piece is before it:

format:  <length>#<content><length>#<content>...

["abc", "de"]  →  "3#abc2#de"

To decode: read the number up to the #, then take exactly that many characters as the content — never interpreting what's inside. The # is never ambiguous because you only look for it at the length position; the content characters are read by count, not by search. This works even if a piece of data contains #, numbers, or another whole encoded string.

The signs (the design pattern)

• "Serialize / deserialize", "encode / decode", "transmit and reconstruct".
• The data can contain any character (there's no safe separator).
• Shows up strongly in the Trees section (serializing a binary tree is the same principle: recording structure without ambiguity).

Example — Encode and Decode Strings

"Write encode(list) → string and decode(string) → list that work for any content."

Notice the third piece: "a#2#b" contains # and digits — exactly what would break a separator. With length-prefix, it comes back intact, because the decoder counts characters instead of searching for separators.

Why is it O(n)?

• encode: traverses each string once to build the output — O(n) over the total number of characters.
• decode: the pointer i advances through the encoded string without ever going back (reads the number, skips the content) — O(n). Each character is visited once.
• O(n) space for the output, which is unavoidable (it's the result).

Why this lesson matters beyond strings

This is your first design problem: the question isn't "what's the clever trick?", but "what representation avoids ambiguity?". The length-prefix principle — store the length so you don't depend on delimiters — is used in real network protocols and comes back in tree serialization (Trees section). Recognizing "this is a representation problem" is already half the battle.

Summary

• Encoding is a design/representation problem, not a trick.
• Separators are ambiguous (the data may contain them); length-prefix solves it: count the characters instead of searching for delimiters.
• encode/decode in O(n); the decode pointer never goes back.
• The principle reappears in tree serialization.

Last stop: the synthesis of the String section and the quiz before the final exam.