Encode and Decode Strings — Length-Prefix Framing for Network and Storage

Problem and Topic Statement#

Encode and Decode Strings (LeetCode 271) — design an algorithm to encode a list of strings into a single string that can be sent over the network, and another algorithm to decode the original list. The strings can contain any of the 256 valid ASCII characters (or arbitrary Unicode), and your encoding must be lossless and robust against ambiguity.

What makes this question deceptively interesting is that the obvious answer — "join with a delimiter" — fails the moment any input string contains the delimiter. Solving it correctly is exactly how real-world wire protocols frame variable-length payloads, which is why the question shows up so frequently at Meta, Google, Amazon, and infrastructure-heavy teams.

Why This Topic Matters#

Length-prefix framing is not a string algorithm trick; it is the core idea behind HTTP chunked transfer encoding, gRPC and Protobuf wire formats, MessagePack, BSON, the WebSocket protocol, and countless binary serialisation schemes. If you have ever wondered why HTTP/1.1 sends Content-Length in headers or why Kafka messages start with a 4-byte length prefix, this problem is the toy version of those decisions.

Interviewers at Meta, Amazon, and Google ask this question to verify three things at once. First, that you understand why naive delimiter approaches fail (they always do, eventually, on adversarial input). Second, that you can design a protocol that round-trips losslessly across machines. Third, that you can write parser code that handles edge cases — empty strings, long strings, Unicode, repeated delimiter characters — without crashing.

In production this pattern surfaces every time you serialise a list of variable-length records to disk or wire. Length-prefixed framing is also the foundation of TLV (type-length-value) encodings used in BER (Basic Encoding Rules) for X.509 certificates, ASN.1, and most low-level network protocols.

The Core Insight#

The natural impulse is to join the strings with a separator like , or #. This fails because any input that contains the separator becomes ambiguous. Escaping the separator inside payloads is possible but adds parsing complexity that grows quickly with character classes.

The correct approach is length-prefix framing: for each string, emit length + delimiter + payload. The delimiter is unambiguous because the parser reads it only after consuming exactly length bytes. The delimiter inside a payload is harmless because the parser never reads past the declared length.

Concrete encoding:

encode(["abc", "de"])  =>  "3#abc2#de"

Decoding logic:

1. Read characters until you hit the delimiter; parse them as the length L.
2. Skip the delimiter.
3. Read exactly L characters as the payload.
4. Repeat from step 1 until the input is exhausted.

The payload itself is opaque to the parser; the delimiter could occur inside it without confusing anything.

This generalises to binary protocols. Replace the ASCII length with a fixed-width integer (4 bytes is common) and you have the standard framing for HTTP, Kafka, and dozens of others. Replace the delimiter with a literal byte separator that never appears in length encodings (since lengths are pure digits, anything else is unambiguous in the ASCII case).

For Unicode strings, the byte length and the character count differ. Decide which one you encode and stick with it consistently. Encoding byte length is simpler because reading exactly L bytes works regardless of multi-byte sequences.

Visual Dry Run / Worked Example#

Encode ["leet", "code", "love", "you"]:

"4#leet" + "4#code" + "4#love" + "3#you"
= "4#leet4#code4#love3#you"

Decode "4#leet4#code4#love3#you":

i=0: read until '#': "4" -> len=4
     i moves to 2 (after '#')
     read 4 chars: "leet"
     i = 6
i=6: read until '#': "4" -> len=4
     i = 8, read "code", i = 12
i=12: "4#love" -> "love", i = 18
i=18: "3#you" -> "you", i = 23

Result: ["leet", "code", "love", "you"].

Adversarial test: encode ["a#b", "##", ""]:

"3#a#b2###0#"

Decode:

i=0: len=3, payload="a#b", i=5
i=5: len=2, payload="##", i=10
i=10: len=0, payload="", i=12

Result: ["a#b", "##", ""]. The hash characters inside payloads do not confuse the parser because it always reads exactly len characters.

Solution (Optimal)#

Python#

class Codec:
    def encode(self, strs):
        return "".join(f"{len(s)}#{s}" for s in strs)
 
    def decode(self, s):
        res = []
        i = 0
        while i < len(s):
            j = s.index('#', i)
            length = int(s[i:j])
            res.append(s[j + 1:j + 1 + length])
            i = j + 1 + length
        return res

JavaScript#

class Codec {
  encode(strs) {
    let out = "";
    for (const s of strs) {
      out += s.length + "#" + s;
    }
    return out;
  }
 
  decode(s) {
    const res = [];
    let i = 0;
    while (i < s.length) {
      const j = s.indexOf("#", i);
      const length = parseInt(s.slice(i, j), 10);
      res.push(s.slice(j + 1, j + 1 + length));
      i = j + 1 + length;
    }
    return res;
  }
}

Complexity: encode is O(N) total characters; decode is O(N) by construction. Space O(N).

Binary length-prefix variant (Python)#

import struct
 
def encode_binary(strs):
    out = bytearray()
    for s in strs:
        b = s.encode('utf-8')
        out += struct.pack('>I', len(b))
        out += b
    return bytes(out)
 
def decode_binary(buf):
    res = []
    i = 0
    while i < len(buf):
        length = struct.unpack('>I', buf[i:i + 4])[0]
        i += 4
        res.append(buf[i:i + length].decode('utf-8'))
        i += length
    return res

This is the production form used by gRPC, Kafka, and most binary protocols.

Common Mistakes#

• Joining with a delimiter alone (e.g. , or null byte) — fails on any input containing the delimiter.
• Escaping the delimiter inside payloads — works but is far more error-prone than length-prefix framing and harder to test exhaustively.
• Reading the length character-by-character without finding the delimiter index first — slower in interpreted languages and prone to off-by-one.
• Confusing byte count with character count for Unicode — pick one and document it. UTF-8 byte length is the safer default.
• Allocating new buffers per record on decode — slice in place when possible.
• Forgetting empty strings — 0# is a valid record and your parser must handle it without infinite-looping.

Interview Tips#

Pre-empt the delimiter trap. Many candidates start with delimiter-only encoding; show you anticipated this by mentioning it as a flawed approach in the first thirty seconds.

Walk through the encode/decode protocol on paper before coding. Use a tiny example with delimiter characters in payloads ("a#b") to demonstrate correctness.

Mention that this is exactly how real protocols work. Naming HTTP chunked transfer, Protobuf, or Kafka shows industry awareness and earns favourable signal at infrastructure-heavy companies.

Address Unicode explicitly. State whether your length is byte count or character count and why. Most production systems use byte count because it works seamlessly with stream readers.

Follow-up Questions#

1. What if the strings can be gigabytes large? Stream the encoder and decoder. Read the length, then read exactly that many bytes from the stream. Never load the whole payload into memory.
2. How do you handle versioning? Add a version byte at the start of the encoded blob. Future versions can change framing without breaking older decoders that check the version first.
3. What if the network can corrupt bytes? Add a checksum or CRC32 per record. Length-prefixed framing combines naturally with type-length-value (TLV) framing.
4. How would you handle a very large list? Stream the records as they are produced. The framing protocol does not require a known total length up front.
5. Compare to JSON serialisation. JSON requires escaping every quote and backslash inside strings; length-prefix framing requires no escaping but is not human-readable. Trade-off depends on use case.

Key Takeaways#

• Length-prefix framing is the canonical solution to encoding variable-length payloads losslessly; it has zero ambiguity by construction.
• Delimiter-only approaches always fail on adversarial input; escaping helps but is brittle and hard to test exhaustively.
• The same idea powers HTTP chunked transfer, Protobuf, gRPC, Kafka, MessagePack, and ASN.1 BER — knowing it pays off well beyond interviews.
• Decide between byte length and character length consciously; UTF-8 byte length is the safer production default.
• Streaming-friendly decoders read the length, then read exactly that many bytes — never assume the entire blob is buffered.
• Mentioning the connection to real protocols during the interview earns major signal at infrastructure-heavy teams.