4.4.6 — Encode and Decode Strings

LeetCode 271 · Medium · ★ Blind 75

The problem

Turn a list of strings into one string, and turn it back.

codec.decode(codec.encode(["lint", "code", "love", "you"]))
# must give back ["lint", "code", "love", "you"]

Up to 100 strings, each up to 200 characters. Each string may contain any of the 256 ASCII characters. That last line is what makes the problem.

In plain English, you want to bundle a bunch of strings together into a single string to send it over the internet or save it to a file. Then, another program needs to read that single string and get back the exact original list of strings. The difficulty is that the strings can contain ANY characters, including any special delimiters you might try to use.

The pattern

The first idea is to join with a separator:

def encode(strs): return "#".join(strs)
def decode(s):    return s.split("#")

Now feed it ["a#b", "c"]. It encodes to "a#b#c" and decodes to ["a", "b", "c"]. Three strings out, two in. Nothing crashed. The data is just wrong.

This is called delimiter collision. Picking a rarer separator does not fix it — every character is a legal character in the data, so there is no safe separator. Once you accept that, the answer is forced:

If you cannot mark where a string ends, say in advance how long it is.

Think of it like packing boxes inside a moving truck. If you just shove everything in and say "a red sticker means a new box starts here", what happens when someone packs their red sticker collection? The movers will get confused and tear apart the box. Instead, you need a manifest that says "The next box is exactly 5 cubic feet". Then the movers just measure 5 cubic feet, completely ignoring what's inside, and they never get confused.

The idea

Write each string as its length, then a marker, then the string.

["lint", "code"]   →   "4#lint4#code"
["a#b", "c"]       →   "3#a#b1#c"

Decoding never hunts for a delimiter inside the data. It reads digits until it hits #, converts them to a number, and then takes exactly that many characters, whatever they are. The # inside "a#b" is swallowed as ordinary content, because the reader was told to take 3 and just took 3.

Length first, then the payload taken blind. This is how nearly every real protocol frames a message.

An interviewer will ask: if no character is safe, how is # safe? Because it is not separating the data. It only ever ends a run of digits, at a position the reader is already standing on, and a digit is never #. Safety comes from position, not from rarity.

The solution

Python

class Codec:
    def encode(self, strs: List[str]) -> str:
        return ''.join(f"{len(s)}#{s}" for s in strs)

    def decode(self, s: str) -> List[str]:
        result, i = [], 0
        while i < len(s):
            j = i
            while s[j] != '#':                       # walk over the digits
                j += 1
            length = int(s[i:j])
            result.append(s[j + 1 : j + 1 + length])
            i = j + 1 + length
        return result

TypeScript

function encode(strs: string[]): string {
  return strs.map(s => `${s.length}#${s}`).join('');
}

function decode(s: string): string[] {
  const result: string[] = [];
  let i = 0;
  while (i < s.length) {
    let j = i;
    while (s[j] !== '#') j++;
    const length = Number(s.slice(i, j));
    result.push(s.slice(j + 1, j + 1 + length));
    i = j + 1 + length;
  }
  return result;
}

i always sits on the first digit of the next record. j ends up on the #. The slice s[i:j] stops before j, so it holds the digits and not the marker.

The two + 1s are where everybody makes a mistake. The payload starts at j + 1, one past the #. The next record starts at j + 1 + length. Drop either + 1 and the parse slides one character out of step — you either get strings with a leading #, or an int("") crash on the next round. Your Report 1 recorded this exact bug under the name decode pointer sync.

In Python, build the encoded string with ''.join(...). Using res += ... in a loop copies the whole accumulated string every time, because strings are immutable, and that is O(k^2) in the total length.

Code Walkthrough (Decode)

1. result, i = [], 0: i is our main pointer tracking where we are in the encoded string.
2. while i < len(s):: Keep decoding until we reach the end.
3. j = i; while s[j] != '#': j += 1: Send a scout pointer j forward until it hits the # marker. Everything from i to j-1 is the length number.
4. length = int(s[i:j]): Extract the number of characters we need to read.
5. result.append(s[j + 1 : j + 1 + length]): Take exactly length characters after the # and add it to our output. We read completely blind, ignoring any # signs inside this block.
6. i = j + 1 + length: Jump our main pointer forward so it lands on the first digit of the next string's length prefix.

Trace

s = "3#a#b1#c"

step	i	j	length	slice	new i
1	0	1	3	s[2:5] = "a#b"	5
2	5	6	1	s[7:8] = "c"	8

i reaches 8, the loop ends, and the # at index 3 was never looked at.

Complexity

O(N) both ways for N total characters. The digit scan runs at most three times per record here, so it is not a hidden linear cost.

Time Complexity:

• Encode: We iterate over every string and measure its length, then join them. Joining string pieces of total length N takes O(N) time.
• Decode: The i pointer and j pointer each move strictly forward. Every character of the encoded string is visited at most twice (once by j looking for #, and once when slicing the payload). Slicing takes time proportional to the payload length. Summing all payloads gives O(N) time. Space Complexity:
• Encode: The output string has length O(N). Aside from the output, we store string fragments in a list before joining, which also takes O(N) extra memory.
• Decode: We create a result list containing substrings that total length O(N). So the extra space is O(N).

The alternative — escaping

The other real answer: pick a delimiter and escape every occurrence of it inside the data. Double a colon to mean a literal colon, and use :; to end a record. CSV does this with quotes; shells do it with backslashes.

Length prefixing wins when you know the length up front, which you do here, and its decoder never inspects the payload at all. Escaping wins when the data is produced bit by bit and you cannot know how long it will be. HTTP has both, which is why Content-Length and chunked transfer encoding both exist.

Edge cases

[""] encodes to "0#" and decodes to a zero-length slice, so the empty string needs no special case. That is a sign the design is right — a separator scheme cannot even tell [""] from []. An empty list encodes to "" and the loop never runs.

A string of pure digits is fine: ["123"] → "3#123". The reader stops looking for # the moment it has a length.

Where this goes next

This is not a puzzle. Length prefixing is how real systems frame messages:

• HTTP sends Content-Length: 4096 then exactly 4,096 bytes, which may contain anything. Chapter 5.6 covers what happens when that length lies.
• TCP does no framing at all, which is why every socket server has to do this itself. Chapter 5.9.
• Protocol Buffers encode tag, length, value.
• Databases store a variable-length column as a length header plus bytes. Chapter 7.3.

The idea: self-describing data beats delimited data whenever the payload is unrestricted.

What the interviewer will push on

"Why not join with a comma?" The data may contain a comma, and no character is safe, so prefix the length instead.

"Why is # safe then?" Position, not rarity.

"How would you make it streaming?" You need the length up front, so buffer the string or switch to chunked framing — write a length, write that many bytes, repeat, finish with a zero. That is HTTP chunked encoding.

"What if the encoded string is corrupt?" A bad length walks the reader off the end. Real parsers check j < len(s) and j + 1 + length <= len(s). On a judge those guards are noise; in a network parser their absence is a denial-of-service bug.

One thing to volunteer: point out that the empty string needs no special case. Most people add a branch for it.

Next: 4.4.7 Product of Array Except Self — no hashing at all, and a different way to kill a nested loop.