Encode and Decode Strings

The problem

Design encode(strs: string[]): string and decode(s: string): string[] so that decode(encode(strs)) restores the original list.

Strings may contain any UTF-8 / ASCII including commas, #, newlines. Empty strings allowed.

["lint","code","love","you"] → somehow one string → same list
["","a"] must work

What fails

• Join with "," — strings may contain commas.
• Join with rare delimiter without escaping — still fragile.
• JSON.stringify — works in JS interviews sometimes, but they want you to invent a codec.

Length-prefix encoding

Encode each string as `${length}#${str}` concatenated.

["ab","c"] → "2#ab1#c"
["", "x#y"] → "0#3#x#y"

Decode: read digits until #, parse length, slice that many chars, repeat.

function encode(strs: string[]): string {
  let out = "";
  for (const s of strs) {
    out += `${s.length}#${s}`;
  }
  return out;
}

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

Time	O(total characters)
Space	O(total) for output

Chunk walk "2#ab1#c"

i	len	payload	next i
0	2	ab	4
4	1	c	7

Escaping alternative

Delimiter + escape (\ for \ and delimiter). More error-prone to implement under time pressure. Length-prefix is cleaner.

Edge cases

• Empty list → "" → decode []
• List of empty strings ["",""] → "0#0#"
• Strings with # and digits
• Very long strings — length as decimal is fine

Common mistakes

• Using split('#') — breaks when payload contains #
• Not scanning multi-digit lengths (10# + 10 chars)
• Off-by-one on slice end

Interview delivery

1. Forbid naïve join.
2. Propose length + separator.
3. Implement encode/decode carefully.
4. Test empties and embedded #.
5. Linear time.

Mental model

You need a self-describing stream: know where each string ends without scanning for a forbidden delimiter. Length prefixes are the standard network-protocol move (think TLV frames).

Escaping works but is harder to get right under time pressure (escape the escape character too).

Test vectors to run mentally

• []
• ['']
• ['','']
• ['#','12#x']
• ['a'*100] multi-digit length

Out-loud answer

“Encode each string as length, hash, payload. Decode by scanning digits until hash, parse length, slice payload. Handles empties and embedded delimiters. Linear in total size.”

Complexity table

Scheme	Correct with # inside?	Empty strings?	Notes
join comma	no	awkward	reject
escape delimiter	yes if careful	yes	easy to bug
length-prefix	yes	yes	preferred
JSON.stringify	yes in JS	yes	may be disallowed

Interview delivery

1. Need lossless list codec.
2. Length + # + payload.
3. Decode scanner.
4. Test empties.
5. Linear time.

Related

• Group Anagrams
• Serialize Deserialize Binary Tree
• Valid Parentheses
• LRU Cache
• JavaScript Interview Guide

Further reading

• LintCode 659 — Encode and Decode Strings
• MDN: String.prototype.slice