Encode and Decode Strings: The Length-Prefix Trick
How to serialize a list of strings into one string and parse it back — the length-prefix protocol, with JavaScript code, a decode walkthrough, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Design a way to squeeze a list of strings into a single string, then rebuild the original list from that single string. That is the entire task — no built-in JSON.stringify, no arrays of arrays sneaking through, just characters in and characters out.
It sounds trivial until you realize the strings can contain anything: spaces, commas, newlines, even the exact character you were planning to use as a separator. The moment your data can look like your delimiter, naive join/split falls apart.
The fix is a tiny protocol that real systems use everywhere — HTTP bodies, network frames, binary file formats. Learn it once here and you will recognize it for the rest of your career.
The problem
Implement two functions. encode(strs) takes an array of strings and returns a single string. decode(s) takes that string and returns the original array. The only contract: decode(encode(strs)) must equal strs for any input, including empty strings and strings full of punctuation.
Input: ["neet", "code", "love", "you"]
encode: "4#neet4#code4#love3#you"
decode: ["neet", "code", "love", "you"] // exactly what we started withThere is no numeric answer to return and no pair to find. The whole difficulty is designing an encoding that survives round-tripping no matter what characters live inside the words.
The brute force baseline
The first idea everyone reaches for is a separator. Pick a character, glue the words together with it, split on it later.
function encode(strs) {
return strs.join("#"); // "neet#code#love#you"
}
function decode(s) {
return s.split("#");
}This passes the friendly example and then dies the instant a word contains #. Encode ["a#b", "c"] and you get "a#b#c". Split that on # and you get ["a", "b", "c"] — three strings where there were two. The delimiter is indistinguishable from the data.
You can try to escape the delimiter, or pick a rarer character, but there is no character guaranteed to never appear in an arbitrary string. Any pure-delimiter scheme is one hostile input away from breaking. That is the trap the problem is built to expose.
The key insight: say how long before you say what
Stop trying to find a separator the data can't contain. Instead, announce the length of each string before the string itself, so the decoder never has to search for a boundary — it can count to it.
The format for each word is:
[length]#[the string]The # is not a separator between words anymore. It is a marker that ends the length number and says "the payload starts on the next character." When decoding, you read digits until you hit #, that gives you a number n, and then you grab exactly n characters — no scanning, no guessing. Whatever those n characters are, including more # symbols, they get copied verbatim.
Encoding ["a#b", "c"] this way gives "3#a#b1#c". The decoder reads 3, jumps past the #, and takes the next 3 characters — a, #, b — as one payload. The inner # never confuses it, because the length told it exactly how far to read. This is the length-prefix pattern, and it is delimiter-collision-proof by construction.
The optimal solution
Encoding is a single pass that appends length + "#" + word for each string. Decoding walks the encoded string with two indices: i marks the start of the current chunk, and j scans forward to find the #.
class Codec {
// Encodes a list of strings to a single string.
encode(strs) {
let res = "";
for (let s of strs) {
// Format: [length][#][payload]
res += s.length + "#" + s;
}
return res;
}
// Decodes a single string to a list of strings.
decode(s) {
let res = [], i = 0;
while (i < s.length) {
let j = i;
while (s[j] !== "#") j++; // find delim
let length = parseInt(s.substring(i, j));
let str = s.substring(j + 1, j + 1 + length);
res.push(str);
i = j + 1 + length; // advance past this chunk
}
return res;
}
}Two lines carry the whole idea. s.substring(j + 1, j + 1 + length) reads the payload starting right after the # and stops after exactly length characters — that slice is where delimiter safety comes from. Then i = j + 1 + length teleports the read pointer to the start of the next chunk, so the outer while loop processes one word per iteration.
Walkthrough
Trace decode("3#a#b1#c"), the encoding of ["a#b", "c"]. The string indexes as 3(0) #(1) a(2) #(3) b(4) 1(5) #(6) c(7).
| i | j scans to # | s[i..j) | length | substring(j+1, j+1+length) | res | next i |
|---|---|---|---|---|---|---|
| 0 | j = 1 | "3" | 3 | substring(2, 5) = "a#b" | ["a#b"] | 1+1+3 = 5 |
| 5 | j = 6 | "1" | 1 | substring(7, 8) = "c" | ["a#b", "c"] | 6+1+1 = 8 |
At i = 8 the outer loop condition i < s.length (8 < 8) is false, so decoding stops and returns ["a#b", "c"] — the original list, inner # and all. Notice row 1: even though s[3] is #, the decoder never treated it as a boundary, because it was busy counting out 3 payload characters, not searching for a separator.
Complexity
Let n be the total number of characters across all strings (plus the small length-prefix overhead).
| Operation | Time | Space | Why |
|---|---|---|---|
| encode | O(n) | O(n) | one pass appending each character once into the result |
| decode | O(n) | O(n) | i and j together advance through the string exactly once |
Decode looks like it has a nested loop, but it isn't quadratic: across the whole run, the inner j pointer only ever moves forward and never resets behind i. Every character is visited a constant number of times, so both directions are linear. The space is the output — the encoded string or the decoded array — which is unavoidable.
Common mistakes
- Using a bare delimiter with
join/split. Works in the demo, breaks on any string containing that character. There is no "safe" delimiter for arbitrary text. - Putting the
#before the length. The decoder finds the length by scanning for the first#; if the marker comes first,s.substring(i, j)is empty andparseIntreturnsNaN. - Off-by-one on the payload slice. The payload starts at
j + 1, notj(which is the#itself). Reading fromjprepends a stray#to every decoded word. - Forgetting empty strings.
""encodes as"0#". The decoder reads length 0, slices zero characters, and pushes"". Nothing special needed — but only because the length prefix handles it. A delimiter scheme would silently lose it. - Assuming single-digit lengths. A 12-character string encodes as
"12#...". Because you scan digits until#rather than reading one char, multi-digit lengths just work — but a fixed-width prefix would not.
Where this pattern shows up next
Length-prefixing is how you frame data whenever a stream has no natural boundaries: HTTP Content-Length headers, TCP message framing, protocol buffers, and most binary file formats all announce a size before the bytes. The two-pointer scan in the decoder — i anchoring a window while j finds its far edge — is the same chunk-reading move you will use across string-parsing problems.
Step through the whole encode-then-decode cycle in the Encode and Decode Strings visualizer to watch the length prefixes light up and the decode pointers walk each chunk.
FAQ
Why not just separate the strings with a comma or a special character?
Because no single character is guaranteed to be absent from arbitrary input. If a word contains your delimiter, split cuts it in the wrong place and you get more strings than you started with — encode ["a,b", "c"] with a comma and decode gives you three pieces. The length-prefix scheme sidesteps this entirely: the decoder counts characters instead of searching for a separator, so the data can contain the # marker freely.
How does decode handle a # that appears inside a word?
It never looks for # inside a payload. It only scans for the first # to end the length number, then reads exactly that many characters as the payload without inspecting them. In "3#a#b...", after parsing length 3 the decoder grabs the next 3 characters (a, #, b) as a literal slice. The inner # is just one of those characters and is copied verbatim.
What is the time and space complexity?
Both encode and decode run in O(n) time and O(n) space, where n is the total length of all strings plus the length prefixes. Encode touches each character once while building the result. Decode advances two pointers, i and j, that together sweep the string a single time — the inner scan for # never revisits characters behind i, so it stays linear rather than quadratic. The space is the output itself.
How do empty strings survive the round trip?
An empty string encodes as "0#" — length 0 followed by the delimiter and zero payload characters. On decode, the parser reads the length 0, slices substring(j+1, j+1) which is "", and pushes an empty string into the result. Because the count is explicit, empty strings are preserved exactly. This is one of the cases a naive delimiter-only approach quietly drops.
Could I use a longer or fixed-width delimiter instead of a length prefix?
You could try a rare multi-character sequence, but it only lowers the odds of a collision, it does not eliminate them — any sequence you pick can still appear in the data. A fixed-width length prefix (say, always 4 digits) works but caps the maximum string length and wastes space on short words. The variable-length [digits]#[payload] format is the sweet spot: unbounded lengths, minimal overhead, and zero collision risk.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.