DSA problem
Encode and Decode Strings
Design an algorithm to encode a list of strings to a single string, and another algorithm to decode that single string back to the original list. The encoder and decoder run as separate machines, so the decoder receives only the encoded blob — it has no side-channel access to the original list length or any per-string metadata. Your scheme must round-trip any list of strings, including the empty list, empty strings, and strings containing any Unicode characters (delimiters, digits, control bytes — anything).
The naive idea of joining with a sentinel character (say , or a NUL byte) falls apart the moment a real string contains that character. The classic robust scheme is a length-prefix encoding: emit each string as len + '#' + body, where len is the decimal byte length and # is a fixed delimiter. The delimiter is unambiguous because the decoder always knows it is reading digits until it hits the first #, after which it copies exactly len bytes regardless of what they contain.
This shape is essentially the same trick used in Netstrings and HTTP Content-Length framing — when the payload can be arbitrary, you tell the receiver its size up front rather than relying on in-band markers. It is O(N) in total bytes for both directions, with no extra space beyond the output buffer, and it cleanly handles edge cases like [""] (encoded as "0#") and [] (encoded as "").
In implementation terms, encode simply concatenates str(len(s)) + "#" + s for each s. decode walks an index pointer i, scans forward to the next #, parses the digit run as the length L, then slices L characters starting after the #. Repeat until the pointer reaches the end. No regex, no escaping, no state machine — just two cursors and a length.
Examples
strs = ["Hello","World"]["Hello","World"]strs = [""][""]strs = ["a#b","12#34"]["a#b","12#34"]Constraints
- 1 <= strs.length <= 200
- 0 <= strs[i].length <= 200
- strs[i] contains any possible characters out of 256 valid ASCII characters.
- The encode and decode functions must round-trip exactly.
- You may not use any built-in serializer such as eval / pickle / JSON.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.