Blind 75 Visualized

#11 · Arrays & Hashing

Encode and Decode Strings

Design an algorithm to encode a list of strings into a single string, and decode it back to the original list. The strings can contain any characters, so no character is safe to use as a plain separator.

MediumLeetCode
  • Active
  • Found
  • Window
  • Visited
  • Rejected
step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Length-prefixed records (framing)

Write each string as <length><marker><bytes>. The decoder reads the length first and then consumes exactly that many characters, so it never has to look at, or escape, the content. This is how network protocols and file formats (HTTP chunked bodies, netstrings, Redis RESP) frame data.

Memory layout

One flat string/byte buffer, built with a single pass. Fixed-width headers make the layout random-access friendly: each record start can be found with arithmetic and no scanning.

OperationCost
encodeO(total characters)
decodeO(total characters)
extra spaceO(total characters) for the result

Escaping (delimiter + escape character)

Keep a separator but make it unambiguous by escaping occurrences of the separator and of the escape character inside the data. The decoder is a small state machine.

Memory layout

A flat buffer that is slightly larger than the input (each special character costs one extra character). Decoding must look at every character.

OperationCost
encodeO(total characters)
decodeO(total characters), state machine

Why it fits

  • The requirement "any character may appear" rules out any plain separator: whatever you pick, some string can contain it. You need either escaping or a count of how much to read.
  • A length prefix converts the problem from "find the boundary by inspecting content" into "skip a known number of characters", which is correct for arbitrary content, including empty strings, and needs no escaping.
  • Decoding runs in one pass with O(1) work per record, since the header tells you exactly where the next record starts.

Why alternatives degrade

join / split with a separator:
Breaks as soon as any string contains the separator, and cannot tell [] from [""].
Choose a "rare" separator:
There is no safe character in the general case: a test can always include it. Even multi-character separators can appear in the data.
JSON serialization:
Correct and the practical choice in production, but it just shifts the same problem (quoting and escaping) onto a library; the interview is asking you to design the framing yourself.

Four approaches, from naive to production

1 · beginner

Join with a separator, split on it

time O(total characters)space O(total characters)

Encode with join(":") and decode with split(":"). It is the first idea everyone has, and it is broken whenever a string contains the separator.

string encode(vector<string>& strs) {
    string out;
    for (size_t i = 0; i < strs.size(); i++) out += (i ? ":" : "") + strs[i];
    return out;
}

vector<string> decode(string s) {
    vector<string> out; string cur;
    for (char c : s) { if (c == ':') { out.push_back(cur); cur.clear(); } else cur += c; }
    out.push_back(cur);
    return out;
}

Flaws & bottlenecks

  • Incorrect when any string contains the separator: the demo shows ["we","say",":","yes"] decoding to five strings.
  • Cannot distinguish an empty list from a list holding one empty string (both encode to "").
  • No way to detect or recover from corruption.

Interviewer cross-questions

Can you pick a separator that never appears?

Say: No. The problem says strings may contain any character, so whatever separator you choose, a test case can contain it. A longer "unlikely" separator only lowers the probability; it is still wrong for adversarial input.

What are the other failure cases besides the separator?

Say: The empty list versus [""] ambiguity (both become the empty string with join), and trailing empty strings in some split implementations (JavaScript keeps them, Java's split(":") drops them unless you pass -1).

When would this be acceptable?

Say: When you control the data and can guarantee the separator never occurs (for example, a CSV of numbers). The moment the content is arbitrary, you need escaping or framing.

2 · intermediate

Escape the separator

time O(total characters)space O(total characters)

Escape the separator and the escape character inside each string, and terminate each string with a separator. The decoder treats the escape character as "take the next character literally".

string encode(vector<string>& strs) {
    string out;
    for (const string& s : strs) {
        for (char ch : s) { if (ch == '/' || ch == ':') out += '/'; out += ch; }
        out += ':';
    }
    return out;
}

vector<string> decode(string s) {
    vector<string> out;
    string cur;
    for (size_t i = 0; i < s.size(); i++) {
        char c = s[i];
        if (c == '/') cur += s[++i];
        else if (c == ':') { out.push_back(cur); cur.clear(); }
        else cur += c;
    }
    return out;
}

Flaws & bottlenecks

  • Escaping must be applied in the right order and handled on both sides, so it is easy to get subtly wrong (escape the escape character first).
  • The decoder is a character-by-character state machine; every character must be inspected.
  • A dangling escape character at the end of a malformed message reads past the end of the input.

Interviewer cross-questions

Why terminate every string with the separator instead of joining?

Say: Joining makes [] and [""] encode the same ("" in both cases). Terminating each string gives [] → "" and [""] → ":", which are distinct, so the empty list round-trips correctly.

Why must the escape character itself be escaped?

Say: Otherwise a string ending with the escape character would swallow the following separator. With "//" for a literal "/", every escape marker is followed by exactly the character it protects.

What is the overhead?

Say: In the worst case (every character is special) the encoded form is about twice as long, which is why length-prefixing, with a bounded overhead per string, is usually preferred.

3 · advanced

Length prefix: "len#payload"

time O(total characters)space O(total characters)

Write each string as its length, a "#", then the string. To decode, read digits up to the "#", then take exactly that many characters.

string encode(vector<string>& strs) {
    string out;
    for (const string& s : strs) out += to_string(s.size()) + "#" + s;
    return out;
}

vector<string> decode(string s) {
    vector<string> out;
    size_t i = 0;
    while (i < s.size()) {
        size_t hash = s.find('#', i);
        size_t len = stoul(s.substr(i, hash - i));
        out.push_back(s.substr(hash + 1, len));
        i = hash + 1 + len;
    }
    return out;
}

Flaws & bottlenecks

  • Length is counted in code units (UTF-16 in JS, bytes in C++), so the sender and receiver must agree on the unit; counting characters on one side and bytes on the other corrupts the stream.
  • Variable-width decimal lengths still require scanning for the "#", although the scan is short.
  • No validation: a corrupted length reads the wrong slice, or past the end, with no error.

Interviewer cross-questions

Why can the payload safely contain "#" or digits?

Say: The decoder never searches inside the payload. It reads the length, which is found by looking only at the first "#" after the current position, then skips exactly that many characters. Content cannot influence where records start.

What about Unicode?

Say: Be explicit about the unit. If encoder and decoder both use the same string type (UTF-16 code units in JS/Java), lengths agree. Across systems, encode to UTF-8 bytes and prefix the BYTE count, then decode bytes before turning them into text.

How does this relate to real protocols?

Say: It is the same idea as netstrings, HTTP chunked transfer, and Redis RESP bulk strings: length-prefixed framing, so receivers can read exact amounts without scanning payloads.

4 · expert

Fixed-width hex header with validation

time O(total characters)space O(total characters)

Use a fixed-width (4 hex digit) length header so decoding needs no delimiter search, reject oversized strings on encode, and validate every header and bound on decode so corrupt input fails loudly.

const int HEADER = 4;
const size_t MAX_LEN = 0xffff;

string encode(const vector<string>& strs) {
    string out;
    for (size_t i = 0; i < strs.size(); i++) {
        if (strs[i].size() > MAX_LEN) throw length_error("string too long");
        char hdr[HEADER + 1]; snprintf(hdr, sizeof hdr, "%04zx", strs[i].size());
        out += hdr; out += strs[i];
    }
    return out;
}

vector<string> decode(const string& s) {
    vector<string> out;
    size_t i = 0;
    while (i < s.size()) {
        if (i + HEADER > s.size()) throw invalid_argument("truncated header");
        size_t len = 0; auto r = from_chars(s.data() + i, s.data() + i + HEADER, len, 16);
        if (r.ec != errc() || r.ptr != s.data() + i + HEADER) throw invalid_argument("corrupt header");
        i += HEADER;
        if (len > s.size() - i) throw invalid_argument("corrupt length");
        out.push_back(s.substr(i, len));
        i += len;
    }
    return out;
}

Flaws & bottlenecks

  • Maximum string length is capped by the header width (65 535 here); larger inputs need a wider header or a variable-length integer.
  • Each record carries 4 characters of overhead even for tiny strings (a variable-length integer would be smaller for short strings).
  • Text-based hex doubles the header size compared with a binary 2-byte length.

Interviewer cross-questions

Why a fixed-width header instead of "len#"?

Say: Fixed width removes the delimiter search and its failure modes: the header is always the next 4 characters, so parsing is O(1) and branch-free, and a missing delimiter cannot make the decoder scan the whole buffer.

How do you handle malformed input?

Say: Check before every slice: the header must be fully present, must parse strictly as hex, and the payload must fit within the remaining input. Throw on failure instead of returning partial data, since a corrupt length otherwise silently desynchronizes every later record.

How would you make this production-grade for binary data?

Say: Operate on bytes (Uint8Array/ByteBuffer): a 4-byte big-endian length followed by the UTF-8 payload, with a version byte and optionally a checksum. It halves the header size, is endian-explicit, and avoids text re-encoding.

Synchronized code walkthrough

Showing: Join with a separator, split on it — shares the player above; click any step to jump.

string encode(vector<string>& strs) {
    string out;
    for (size_t i = 0; i < strs.size(); i++) out += (i ? ":" : "") + strs[i];
    return out;
}

vector<string> decode(string s) {
    vector<string> out; string cur;
    for (char c : s) { if (c == ':') { out.push_back(cur); cur.clear(); } else cur += c; }
    out.push_back(cur);
    return out;
}