Encode and Decode Strings: Length-Prefix Encoding Explained for Coding Interviews
3 views
"Encode and Decode Strings" asks you to design two functions: encode turns a list of strings into one string, and decode turns that single string back into the exact original list. It sounds trivial until you realize the strings can contain any character, including commas, spaces, digits, empty strings, and whatever delimiter you were about to pick. That is the whole point of the question: interviewers want to see whether you notice that a naive delimiter is ambiguous.
Why a delimiter alone fails
Suppose you join with a comma. ["a,b", "c"] and ["a", "b", "c"] both encode to "a,b,c", so decode cannot know which one you meant. Picking a rarer delimiter like "#" or a non-printable character only moves the problem, because the input may contain it. Say this out loud early; it shows you are thinking about correctness, not just the happy path.
Option 1: escaping
You can escape the delimiter inside strings, for example turning "#" into "##" and using "#," as the separator. It works, but the logic is fiddly and it's easy to introduce bugs when an escape character appears at the end of a string. Mention it as a valid approach, then move to something simpler.
Option 2: length prefix (the standard answer)
For each string s, write its length, a separator, then the string itself: len(s) + "#" + s. The list ["leet", "co#de", ""] becomes "4#leet5#co#de0#".
Decoding is a pointer walk. Start at i = 0. Scan forward from i to the next "#" to read the number; call it n. The string is the next n characters after the "#". Append it, move i to the position right after those characters, and repeat until the end. Because you jump exactly n characters, any "#" inside the string is never interpreted as a separator. Empty strings work naturally because their length is 0.
Complexity: both functions are O(total characters) in time, and the output size is the input size plus a few digits per string.
Details worth mentioning
- Use a string builder or list join, not repeated string concatenation, to avoid quadratic time in some languages.
- Parsing the length must read all digits, not just one, since strings can be longer than 9 characters.
- A fixed-width binary length header (for example 4 bytes) is how real network protocols do it; this is a nice follow-up showing you know where the idea comes from.
- An empty list should encode to an empty string and decode back to an empty list.
Testing out loud
Walk through an input that contains the separator, an empty string, and a string longer than ten characters. Interviewers score that kind of deliberate testing highly.
This is a great problem to practice explaining rather than memorizing. If you want support during the real thing, Linkjob AI (https://linkjob.ai) gives real-time help during live job interviews and technical interviews, so you can keep your reasoning structured while you code.