Skip to content
DSAPrep

    ↑↓ to move · Enter to open · Esc to close

    MediumArrays & Hashing

    Encode and Decode Strings

    Design an algorithm to encode a list of strings into a single string. The encoded string is sent over a network and decoded back into the original list of strings.

    Implement encode and decode so that decode(encode(strs)) always reconstructs the original list exactly, no matter what characters the strings contain (including commas, slashes, or other characters you might otherwise be tempted to use as a separator).

    Example 1

    Input: strs = ["lint","code","love","you"]

    Output: ["lint","code","love","you"]

    Explanation: encode(strs) produces one string that decode() parses back into the exact original list.

    Example 2

    Input: strs = [""]

    Output: [""]

    Constraints

    • 0 <= strs.length <= 200
    • 0 <= strs[i].length <= 200
    • strs[i] can contain any valid ASCII character.
    View original on LeetCode ↗

    This isn’t really an efficiency problem — any reasonable approach is linear. The real challenge is correctness: whatever separator you pick between strings, one of the input strings might legally contain that exact separator, and your decoder has no way to tell “end of string” from “this string just happens to contain a comma.”

    Delimiter Join (Broken)

    Time O(n)Space O(n)

    The obvious first idea: join the strings with a separator like a comma, and split on that separator to decode.

    class Codec:
        def encode(self, strs: list[str]) -> str:
            return ",".join(strs)
    

        def decode(self, s: str) -> list[str]:
            return s.split(",")

    This looks fine until a string contains the separator itself:

    encode(["a,b", "c"])   # -> "a,b,c"
    decode("a,b,c")        # -> ["a", "b", "c"]   -- wrong! Original had 2 strings, not 3.

    The encoding is ambiguous — "a,b,c" could have come from ["a,b", "c"], ["a", "b,c"], or ["a", "b", "c"]. No amount of escaping the comma fully closes this hole without extra bookkeeping, so this approach is discarded rather than optimized.

    Length-Prefix Encoding

    OptimalTime O(n)Space O(n)

    Instead of relying on a separator that might collide with the data, prefix each string with its own length followed by a delimiter (any character not used as a digit, e.g. /). Since we know exactly how many characters to read once we know the length, the content of the string — commas, slashes, anything — can never be misread as structure.

    class Codec:
        def encode(self, strs: list[str]) -> str:
            encoded = ""
            for s in strs:
                encoded += str(len(s)) + "/" + s
            return encoded
    

        def decode(self, s: str) -> list[str]:
            result = []
            i = 0
            while i < len(s):
                slash = s.find("/", i)
                length = int(s[i:slash])
                start = slash + 1
                result.append(s[start:start + length])
                i = start + length
            return result

    Watch one decode pass on the statement’s first example: the cursor lands on a length prefix, the slash fixes the count, then exactly that many characters are read into a result slot — the string’s own content never needs to be inspected for structure.

    Encoded string

    i4/lint4/code4/love3/you

    Parsing

    len

    –

    word

    –

    Decoded

    ····
    1 / 13
    currentcomparingresultseen

    encode joins the list with length-prefix delimiters. Each group is a count, a slash, then that many characters, so the decoder never needs to guess.

    Correctness: the length prefix tells the decoder precisely how many characters belong to the current string, so it never has to guess where a string ends by scanning its contents — the string’s own characters, whatever they are, can never be confused with a delimiter.

    Complexity: encoding writes each character of every string exactly once, plus a small fixed-size prefix per string — O(n) time and space, where n is the total number of characters across all strings. Decoding does the same work in reverse — one pass, O(n) time, building an output list that also totals O(n) space.

    More Arrays & Hashing practice