Encode and Decode Strings

Problem

Design two functions that encode a list of strings into a single string and decode it back:

• encode(strs) turns a list of strings into one string.
• decode(s) turns that string back into the original list.

decode(encode(strs)) must reproduce the input for any list. The strings may contain any characters, including any delimiter you might choose, and may be empty. All information must travel inside the encoded string; you may not store state elsewhere.

Examples

• encode(["hello", "world"]) produces some string, e.g. "5#hello5#world", and decode returns ["hello", "world"]. The wire format is your choice; only the round trip matters.
• encode([""]) must decode back to [""], a list holding one empty string, not [].
• encode(["a#b", "#", ""]) must handle strings that contain your delimiter characters.

Constraints

• 0 <= strs.length <= 200, each string up to 200 characters.
• Strings may contain any ASCII character; assume no character is safe to use as a bare separator.
• Encode and decode should each run in O(total characters).

Think about it first

TL;DR

Length-prefix framing ("5#hello") — O(total characters) time for both directions, O(1) extra space beyond the output.

Approach 1 — Brute force

This is a design problem, not an optimization problem: there is no running time to improve, so the goal is a correct encoding. Start with the naive design and fix its correctness.

The naive design joins the strings with a separator character and splits on it.

from typing import List


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

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

Complexity: O(total characters) time, but it is wrong:

• ["a,b"] and ["a", "b"] both encode to "a,b" — the payload can contain the separator.
• [] and [""] both encode to "".

Any fixed separator fails the same way, because the problem guarantees strings may contain any character.

Approach 2 — Escaping

The insight: if the separator can appear in the data, encode literal occurrences differently. Pick an escape character, double it whenever it appears in the data, and let escape-plus-marker mean “end of item.” Terminating every item, instead of separating items, also distinguishes [] from [""]. This is the escaping scheme used by string literals and CSV quoting.

from typing import List


class Codec:
    def encode(self, strs: List[str]) -> str:
        # "/" is the escape char: "//" = literal "/", "/;" = end of item.
        return "".join(s.replace("/", "//") + "/;" for s in strs)

    def decode(self, s: str) -> List[str]:
        res: List[str] = []
        cur: List[str] = []
        i = 0
        while i < len(s):
            if s[i] == "/":
                if s[i + 1] == "/":
                    cur.append("/")      # escaped literal slash
                else:
                    res.append("".join(cur))    # "/;" closes the item
                    cur = []
                i += 2
            else:
                cur.append(s[i])
                i += 1
        return res

Walkthrough on ["a#b", "#", ""] (the question’s third example):

1. Encode: no slashes to double, so items become "a#b/;", "#/;", "/;" → "a#b/;#/;/;".
2. Decode scans left to right: a, #, b are plain; /; closes item → "a#b".
3. # plain; /; closes → "#"; final /; closes an empty item → "". Result: ["a#b", "#", ""].

Complexity: O(total characters) time and output space. The decoder inspects every byte of the payload, and the encoding can double in size on all-slash input.

Approach 3 — Length prefix

The insight: searching for a separator is the source of the problem, so remove the search. Write each string’s length up front, and the decoder skips over the payload without reading it. Payload bytes can be anything, including digits and #. This is length-prefix framing, the same technique network protocols such as HTTP chunked encoding use to delimit binary-safe messages.

from typing import List


class Codec:
    def encode(self, strs: List[str]) -> str:
        return "".join(f"{len(s)}#{s}" for s in strs)

    def decode(self, s: str) -> List[str]:
        res: List[str] = []
        i = 0
        while i < len(s):
            j = s.find("#", i)          # first "#" after the digits
            length = int(s[i:j])
            start = j + 1
            res.append(s[start : start + length])
            i = start + length
        return res

Walkthrough on ["hello", "world"] (the question’s first example):

1. Encode: "5#hello" + "5#world" → "5#hello5#world".
2. Decode at i=0: # found at 1, length = 5, payload s[2:7] = "hello", jump to i=7.
3. At i=7: # at 8, length = 5, payload "world", i=14 = end. Result: ["hello", "world"].

A # inside a payload never confuses the decoder, because find only runs at positions known to be headers. For example, ["2#ab"] encodes to "4#2#ab", and after reading length = 4 the entire "2#ab" is consumed without inspection.

Complexity: O(total characters) for both encode and decode, with output-sized space. The header adds only O(log L) characters per string, and no payload byte is inspected, giving better constants than escaping.

Common pitfalls

• Any bare-delimiter scheme fails, whatever character you pick, because payloads are unrestricted.
• Conflating [] with [""]: a separator placed between items encodes both as "". Terminate every item (Approach 2), or use length prefixing, which distinguishes "" from "0#".
• In the length-prefix decoder, assuming the length is a single digit. "12#hello, world" needs find, not s[i] alone.
• Off-by-one on the jump: the next header starts at start + length, not start + length + 1, because there is no separator after the payload.

Pattern takeaway

When data must embed arbitrary data, in-band separators do not work. The two reliable answers are escaping (make the separator unambiguous) and length-prefix framing (make searching unnecessary). Prefer the length prefix: it is self-describing, binary-safe, and linear with no rescanning, and it generalizes from interview problems to real wire protocols.