Encode and Decode Strings — InterviewPrepKit

Solving tips

Any fixed separator fails because payloads may contain that character; use length-prefix framing instead ('5#hello').
The decoder reads digits up to the '#', then jumps exactly length bytes, never inspecting the payload, so embedded digits or '#' are safe.
Length-prefix naturally distinguishes [] from [''] and [''] from other empties; a bare join cannot.
Off-by-one: the next header starts at start+length (no trailing separator); target O(total characters) for both directions.

Problem

Design a pair of functions to ship a list of strings across a network as one string:

encode(strs) turns a list of strings into a single string.
decode(s) turns that single string back into the original list, exactly.

The round trip decode(encode(strs)) must reproduce the input for any list — the strings may contain any characters (including whatever delimiter you were tempted to use), and may be empty. You may not stash state on the side; all information must travel inside the encoded string itself.

Examples

encode(["hello", "world"]) → some string, e.g. "5#hello5#world" → decode → ["hello", "world"] — the exact wire format is yours to choose; only the round trip matters.
encode([""]) → must decode back to [""], a list holding one empty string — and not to [].
encode(["a#b", "#", ""]) → must survive strings that contain your delimiter characters.

Constraints

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

Think about it first

Hint 1

`",".join(strs)` breaks the moment a string contains a comma. Why does *every* fixed separator have this problem, no matter how exotic the character?

Hint 2

Two classic ways out: make the separator unmistakable by *escaping* it inside data, or remove the need to search for a separator at all by announcing, up front, how far to read.

Hint 3

Prefix each string with its length plus a sentinel, e.g. `"5#hello"`. The decoder reads digits up to `#`, then consumes exactly that many characters as payload — anything inside the payload, including digits and `#`, is never inspected.

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 pure design problem — there is no algorithm to speed up — so the ladder starts at the naive design and fixes its correctness.

The naive design: glue the strings together with a separator character and split 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’s wrong, and no constraint tuning fixes that:

["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 data, make occurrences in data look different: pick an escape character, double it whenever it appears literally, and let escape-plus-marker mean “end of item.” Terminating every item (rather than separating items) also distinguishes [] from [""]. This is the classic 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):

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

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

Approach 3 — Length prefix

The insight: searching for a separator is the whole problem — so stop searching. Announce each string’s length up front, then the decoder jumps over the payload without reading it; payload bytes can be anything, including digits and #. This is length-prefix framing, the same idea network protocols (e.g. 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):

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

Why a # inside a payload never confuses it: the decoder only runs find at positions it knows are headers — e.g. ["2#ab"] encodes to "4#2#ab", and after reading length = 4 the entire "2#ab" is consumed blindly.

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

Common pitfalls

Any bare-delimiter scheme, however exotic the character — the problem’s whole point is that payloads are unrestricted.
Conflating [] with [""]: separator-between joins encode both as ""; terminate every item (Approach 2) or note that length-prefix naturally distinguishes "" vs "0#".
In the length-prefix decoder, assuming the length is one 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 — there is no separator after the payload.

Pattern takeaway

When data must embed arbitrary data, in-band separators are a losing game; the two industrial-strength answers are escaping (make the separator unmistakable) and length-prefix framing (make searching unnecessary). Prefer the length prefix: self-describing, binary-safe, and linear with no rescanning — and it generalizes from interview problems to real wire protocols.