Encode and Decode Strings: A Design Challenge
The Prompt
Design an algorithm to encode a list of strings to a single string. The encoded string is then sent over the network and is decoded back to the original list of strings. Please implement `encode` and `decode` methods.
Understanding the Problem
You must flatten a list of strings into one string and later recover the exact list — including empty strings and strings containing any character. The tempting approach, joining with a delimiter like a comma, breaks the moment a string contains the delimiter itself: the decoder cannot tell a real comma from a separator.
The robust fix is to stop searching for a character that "cannot appear" and instead tell the decoder how far to read. Prefix each string with its length plus a marker — "neet" becomes "4#neet". The decoder reads the number, skips the '#', then consumes exactly that many characters, so the payload's content is never inspected at all.
The Interview Flow
Interviewer
How would you design `encode` and `decode` functions to handle a list of strings, especially if the strings could contain any character?
Candidate
The main challenge is knowing where one string ends and the next begins. A simple delimiter like a comma won't work if the strings themselves contain commas.
Interviewer
Exactly. So how do we solve that?
Candidate
We need a way to encode the metadata, specifically the length of each string. A good approach would be to prepend each string with its length followed by a special delimiter. For example, for the list ["hello", "world"], I could encode it as "5#hello5#world".
Interviewer
That sounds robust. Walk me through how the `decode` function would work with that format.
Candidate
The `decode` function would read the encoded string from left to right. It would first parse the number before the "#" to get the length of the upcoming string. Then, it would read that many characters to extract the original string. It would repeat this process until the entire encoded string is consumed.
Interviewer
What if a string is empty?
Candidate
My scheme handles that perfectly. An empty string "" would be encoded as "0#". The decoder would read "0", know to expect zero characters, and correctly reconstruct the empty string.
Interviewer
Excellent. This method is foolproof. Please implement it.
Why is length-prefixing unambiguous?
The decoder's position is always at the start of a header, never inside a payload. It parses digits up to the first '#' — and that '#' is guaranteed to be a header marker, because the decoder jumps over payload bytes wholesale using the parsed length. A '#' or a digit inside a string can never be misread, since the decoder never scans payload characters looking for anything. That invariant (always at a header boundary) is the whole correctness argument.
Encoding is one pass over the input, decoding is one pass over the encoded string — O(N) time in total characters, with O(1) extra space beyond the output. This is not just an interview trick: it is how real protocols (HTTP Content-Length, TLV encodings) frame variable-length data.
Length-Prefixed Encoding Scheme
- **Encode:**
- Initialize an empty string or string builder.
- Iterate through the list of input strings.
- For each string, get its length, convert it to a string, append a delimiter (e.g., "#"), and then append the string itself.
- Concatenate these parts for all strings in the list.
- Return the final concatenated string.
- **Decode:**
- Initialize an empty list for the results.
- Use a pointer `i` to traverse the encoded string.
- From `i`, find the position of the next delimiter "#". The substring between `i` and the delimiter is the length of the next string.
- Parse this length into an integer.
- Extract the original string by taking the substring of that length starting right after the "#".
- Add the extracted string to the results list.
- Update the pointer `i` to the position after the extracted string and repeat until the end of the encoded string is reached.
Try it yourself
Write your solution and run it against 3 test cases.
Your encode → decode round-trip must reproduce the input exactly.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
class Codec {
encode(strs) {
let res = "";
for (const s of strs) {
res += s.length + "#" + s;
}
return res;
}
decode(s) {
const res = [];
let i = 0;
while (i < s.length) {
let j = i;
while (s[j] !== '#') {
j++;
}
const len = parseInt(s.substring(i, j));
res.push(s.substring(j + 1, j + 1 + len));
i = j + 1 + len;
}
return res;
}
}Explanation
Decode "3#cat2#hi" — the encoding of ["cat", "hi"] — one header at a time.
1i = 0: read digits until '#' → length 3. The '#' sits at index 1, so the payload starts at index 2.
2Consume exactly 3 characters: indices 2 through 2 + 3 − 1 = 4 → "cat". Jump i to 5 without ever inspecting the payload.
3i = 5: next header says length 2 → indices 7 through 7 + 2 − 1 = 8 give "hi". i reaches the end — decoded list: ["cat", "hi"].
Complexity Analysis
TIME
O(n)
SPACE
O(n)
Finished working through this one?
Mark it complete to track it on your Data Structures path.