Encode / Decode Strings - Length-Prefix Framing

You’ve used join and split a hundred times. They feel like encode/decode. They aren’t - not when the data can contain the separator. Today’s problem is the interview version of a production problem: message framing. How do you ship a list of arbitrary strings over a single channel and get the exact same list back?

The problem

Design an algorithm to encode a list of strings to a single string. The encoded string is then decoded back to the original list of strings.

Example:

Input:  ["neet", "code", "love", "you"]
Encode: "...."   // any reversible format
Decode: ["neet", "code", "love", "you"]  // must equal input

Constraints that matter:

• Strings may be empty.
• Strings may contain any ASCII character - including whatever delimiter you pick.
• Encode + decode must be a perfect round-trip. No information loss. No reordering. No dropped empties.

The trap: naive join / split

The first instinct is one line:

// Naive - looks right, is wrong
function encode(strs) { return strs.join("#"); }
function decode(s)    { return s === "" ? [] : s.split("#"); }

Works for [“neet”,“code”] → “neet#code” → [“neet”,“code”].

Dies on:

encode(["we", "say", "#", "yes"])
// → "we#say##yes"
decode(...)
// → ["we", "say", "", "yes"]   // WRONG - "#" became an empty string

The delimiter appears inside the data. Split can’t tell “separator” from “payload.” This is the same class of bug as CSV without quoting, or log lines that break when a user types a pipe character.

Approach 1: Escape the delimiter - mostly correct, expensive

Pick a delimiter. Escape every occurrence of it (and the escape character) inside each string. Join. On decode, walk character-by-character and respect escapes.

// Escape-based - correct, O(total chars) with heavy constants
function encodeEscape(strs) {
  return strs
    .map(s => s.replace(/\\/g, "\\\\").replace(/#/g, "\\#"))
    .join("#");
}

function decodeEscape(s) {
  if (s === "") return [];
  const out = [];
  let cur = "";
  for (let i = 0; i < s.length; i++) {
    if (s[i] === "\\" && i + 1 < s.length) {
      cur += s[i + 1]; // take escaped char literally
      i++;
    } else if (s[i] === "#") {
      out.push(cur);
      cur = "";
    } else {
      cur += s[i];
    }
  }
  out.push(cur);
  return out;
}

Handles # and backslashes inside strings. Cost: every encode scans for replacements; every decode walks char-by-char with branchy escape logic. Regex replace also allocates new strings.

Approach 2: Length-prefix framing - correct and fast

Don’t use a character as a boundary. Use a count.

For each JavaScript string, write: <length>#<string data>. Here String.length and slice both count UTF-16 code units—not raw bytes or Unicode code points—so this in-memory JavaScript codec remains consistent even for surrogate pairs. A wire protocol must instead encode to bytes and prefix the byte length. The # terminates only the length field.

// Length-prefix - the interview answer
function encode(strs) {
  let out = "";
  for (const s of strs) {
    out += s.length + "#" + s;
  }
  return out;
}

function decode(s) {
  const out = [];
  let i = 0;
  while (i < s.length) {
    let j = i;
    while (s[j] !== "#") j++;          // find end of length digits
    const len = Number(s.slice(i, j));
    const start = j + 1;
    out.push(s.slice(start, start + len));
    i = start + len;
  }
  return out;
}

Walkthrough for [“we”, “say”, ”#”, “yes”]:

encode:
  "we"  → 2#we
  "say" → 3#say
  "#"   → 1##
  "yes" → 3#yes
combined → "2#we3#say1##3#yes"

decode:
  read len=2, take "we"
  read len=3, take "say"
  read len=1, take "#"     ← the payload IS a hash; fine
  read len=3, take "yes"
→ ["we", "say", "#", "yes"]  ✓

Empty string is natural: length 0, take zero characters → "".

Worked example: empty strings and hashes

Input: ["", “a”, "", “bb”]

encode → "0#1#a0#2#bb"
decode:
  0#  → ""
  1#a → "a"
  0#  → ""
  2#bb → "bb"
→ ["", "a", "", "bb"]  ✓

No special cases. Empties are just length zero. Adjacent empties don’t collapse the way double-delimiters do in naive split.

Benchmark - correctness first, then speed

Recorded from a real Node.js benchmark, 30 runs, median. The script and standalone write-up are not included in this repository.

Correctness suite

Escape fails the empty-list vs one-empty-string ambiguity even though it handles # in content. Length-prefix is the only approach here that is fully lossless on every edge case we tested.

Round-trip median (ms) - HOSTILE strings (contain #, , empty)

Headline: on hostile data at 100K strings, length-prefix is 14.3× faster than escape (median of 30 runs). Naive is omitted from hostile timing - it fails correctness.

Bonus: on safe data at 100K, length-prefix (15.635 ms) even beats naive join/split (28.119 ms). Framing with known lengths can be cheaper than scanning for delimiters across a giant blob.

What breaks if you get this wrong?

• User-generated content in CSV / log formats without quoting → columns shift, rows vanish, security scanners miss fields.
• Custom binary protocols that use a magic byte as separator → the first time payload contains that byte, frames desync forever (classic TCP framing bug).
• Chat systems that join messages with a rare Unicode char “nobody will type” → someone will type it.

Length-prefix (or length-delimited protobuf / RESP bulk strings) is the boring, correct answer production systems already use.

Where you’ve already seen this

• HTTP: Content-Length: 128 then exactly 128 body bytes - not “read until newline.”
• Redis RESP: $5\r\nhello\r\n - bulk string with explicit length.
• Protobuf / gRPC: length-delimited fields on the wire.
• Day 14 message queues: a queue message is a framed payload. Brokers don’t guess where your message ends by looking for a character you “probably” didn’t use.

Connection to previous days

• Day 12 (Group Anagrams): you built a key that must be unambiguous. A bad key merges different groups. A bad codec merges different strings. Same discipline: the encoding must not lose information.
• Day 17 (Keyset pagination): a cursor is a compact encoding of position. If two rows share a timestamp, a naive cursor drops one. Tiebreakers are length/identity framing for “where am I?” - same class of “make the boundary unambiguous.”
• Day 19 (Product except self): both problems reward a reframe. Day 19: don’t divide - multiply both directions. Day 25: don’t split on a character - prefix a length.
• Day 18 (Top K): Big O vs constants. Escape is O(n) like length-prefix, but constants (regex, char walk) lose by 14×. Same lesson as bucket sort being “O(n)” and still slow.

Quiz