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.

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.

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.

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.

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.