Encode and Decode Strings

Design encode/decode for a list of strings so they can round-trip through a single string without ambiguity (delimiter may appear inside strings).

Answers use simple, clear English.

Time: O(n)Space: O(n)

Quick interview answer

Length-prefix encoding: encode as `${len}#${str}` concatenated. Decode by reading the length integer, then the next len characters after '#'. Avoids delimiter collision.

Detailed answer

Length-prefix encoding: encode as `${len}#${str}` concatenated. Decode by reading the length integer, then the next len characters after '#'. Avoids delimiter collision. Naive join with commas fails when strings contain commas. Escaping works but length-prefix is cleaner.

Full explanation

Naive join with commas fails when strings contain commas. Escaping works but length-prefix is cleaner.

Real example & use case

Persisting a multi-part chat message payload into a single Redis string key.

Pros & cons

Pros: unambiguous, O(n). Cons: must carefully parse multi-digit lengths.

Code example

def encode(strs: list[str]) -> str:
    return ''.join(f'{len(s)}#{s}' for s in strs)

def decode(s: str) -> list[str]:
    i, out = 0, []
    while i < len(s):
        j = s.index('#', i)
        n = int(s[i:j])
        out.append(s[j + 1:j + 1 + n])
        i = j + 1 + n
    return out

Practice code · python (view only · no execution)

def encode(strs: list[str]) -> str:
    return ''.join(f'{len(s)}#{s}' for s in strs)

def decode(s: str) -> list[str]:
    i, out = 0, []
    while i < len(s):
        j = s.index('#', i)
        n = int(s[i:j])
        out.append(s[j + 1:j + 1 + n])
        i = j + 1 + n
    return out

#string