038 — Encode and Decode Strings

38 — Encode and Decode Strings

LeetCode 271 · Medium. Design an algorithm to encode a list of strings into a single string, and a corresponding algorithm to decode that single string back into the original list of strings. The strings may contain any characters, including punctuation, whitespace, and any delimiter you might think to use.

---

🍽️ Intuition

Imagine mailing several letters by taping them end-to-end into one long scroll, and telling the recipient "just cut it wherever you see a | symbol." That works great — until one of the letters itself contains a | symbol, and now the recipient cuts in the wrong place and scrambles two letters together. A shipping company that actually has to handle any possible letter content solves this differently: before each letter, they staple a small tag that says "the next 147 characters are one letter." The recipient doesn't hunt for a separator at all — they just read the number on the tag and count out exactly that many characters, no matter what's inside them, then look for the next tag right after.

---

🚩 Pattern-Recognition Cue

"Encode a list of strings into one string, then decode it back, where strings can contain arbitrary characters" is the signal that a plain delimiter (comma, newline, any single "safe" character) is a trap — the input is explicitly allowed to contain that exact character, breaking any decode that searches for it. Whenever a serialization problem says "the data can contain anything, including whatever separator you'd naturally pick," the fix is length-prefixing: store how many characters come next as metadata ahead of the data itself, so decoding never has to search the payload for a boundary — it just counts.

---

🐢 Brute Force

Join all strings with a single delimiter character, and split on that same character to decode.

func encodeBruteForce(_ strs: [String]) -> String {
    return strs.joined(separator: "\u{0}")   // NUL character as a "safe-looking" delimiter
}

func decodeBruteForce(_ s: String) -> [String] {
    return s.isEmpty ? [] : s.components(separatedBy: "\u{0}")
}

Big-O: O(n) time and O(n) space for both encode and decode, where n is the total number of characters across all strings — this is not a speed problem. The issue is correctness: if any input string itself contains the "\u{0}" character, decodeBruteForce will split in the wrong place and silently return the wrong list of strings. It works only under the unstated assumption that the delimiter never appears in the data — an assumption the problem explicitly refuses to guarantee.

---

🚀 Optimal

Prefix each string with its length followed by a # separator. Decoding never searches the string content for anything — it reads digits up to the next # to learn a length, then consumes exactly that many characters, regardless of what they are.

func encode(_ strs: [String]) -> String {
    var result = ""
    for str in strs {
        result += "\(str.count)#\(str)"
    }
    return result
}

func decode(_ s: String) -> [String] {
    var result = [String]()
    let chars = Array(s)
    var i = 0

    while i < chars.count {
        var j = i
        while chars[j] != "#" {
            j += 1
        }
        let length = Int(String(chars[i..<j]))!
        let start = j + 1
        let end = start + length
        result.append(String(chars[start..<end]))
        i = end
    }

    return result
}

Big-O: O(n) time and O(n) space for both encode and decode, where n is the total number of characters — the same asymptotic cost as the brute force, but now correct for every possible input, since the length prefix is read as a fixed, counted quantity rather than searched for as a pattern in the data.

---

🔑 The Key Insight

Both approaches run in O(n) — this isn't a speed upgrade, it's a correctness upgrade, which is just as important a reason to prefer "optimal" over "brute force" as raw runtime is. The delimiter approach conflates the separator with the data: it assumes there's some character the payload will never contain, which the problem statement explicitly rules out. Length-prefixing sidesteps the whole issue by moving the boundary information out of band — the length is metadata about the string, not part of the string, so it can never collide with the string's own content. Once you count out exactly length characters, it doesn't matter if those characters happen to include digits, # symbols, or anything else; you already know exactly where to stop.

---

🔗 Related Chapters

• Arrays & Strings — the character-array traversal both encode and decode are built on.
• Two Pointers — decode's i/j indices walking the character array in tandem (one marking a chunk's start, one scanning ahead for the #) is the same two-index scanning shape, applied to parsing instead of searching.
• Big-O Notation — for the "same Big-O, different guarantee" reasoning that drives this problem's optimal solution.

---

🧸 Memory Sentence

Encode and Decode Strings is stapling a length tag to every letter before taping them into a scroll — count characters instead of hunting for a separator that might already be inside the mail.

---

✅ Check Your Understanding

Suppose one of the input strings is itself something like "5#hello" — digits, a #, and more text, all as literal content. Walk through what decode(encode(["5#hello"])) actually produces with the length-prefixed solution above, and explain why the embedded "5#" inside the string never confuses the decoder.

---

⬅️ Previous: Valid Sudoku · Next: Longest Consecutive Sequence ➡️