Encode and Decode Strings (LC 271)

Pattern: String Design / Delimiter Encoding
Difficulty: Medium
Key Concept: Prefix each chunk with its length and a delimiter that cannot appear in the length token (e.g. 5#hello), so decoding is unambiguous.

Problem Statement

Design an algorithm to encode a list of strings to a single string and decode the string back to the original list of strings.

The encoded string should be compact, and you must handle empty strings and strings that may contain any characters (including delimiters you might choose—so pick a scheme that stays parseable).

Input / Output

• encode(List<String>) → String
• decode(String) → List<String> (same sequence as input)

Example (conceptual)

• ["hello", "world"] → "5#hello5#world"
• decode returns the original list

---

1. Algorithm & Pseudocode

Brute force

Join with a single delimiter (e.g. |) and split on decode. This is fast to write but breaks if any input string contains the delimiter—acceptable only for toy inputs.

encode: return strs joined by "|"
decode: split s by "|"

Optimal (length-prefix)

For each string x, emit len(x) + # + x. Decoding reads digits until #, parses length L, then reads exactly L characters.

encode(strs):
    sb = StringBuilder
    for x in strs:
        sb.append(x.length())
        sb.append('#')
        sb.append(x)
    return sb.toString()

decode(s):
    i = 0
    out = []
    while i < s.length():
        read number j while s[i] is digit
        assert s[i] == '#'; i++
        out.add(s.substring(i, i+j))
        i += j
    return out

---

2. Step-by-Step Analysis (Beginner-Friendly)

1. Why delimiter-only fails If strings can contain |, you cannot split on | without escaping rules.

2. Why length-prefix works After reading the number and #, you know exactly how many following characters belong to the next original string—even if they include #, digits, newlines, or binary-safe UTF-16 units in Java’s char sequence.

3. Empty strings Length 0 encodes as 0# with no following characters—decoder reads zero chars and continues.

4. Why StringBuilder for encode Repeated concatenation with + in a loop creates many intermediate String objects; StringBuilder is linear total time.

---

3. The Dry Run

Encode: ["hi", "5#a"]

piece	emitted
"hi"	2#hi
"5#a"	3#5#a

Full encoded: 2#hi3#5#a

Decode trace

i	read len	after #	take substring	list
0	2	at index after # (pos 3)	s[3..5) = hi	[hi]
5	3	after # at 7	s[7..10) = 5#a	[hi, 5#a]

ASCII

2 # h i 3 # 5 # a
^len ^payload starts--^

---

4. Java Solution

Brute Force (delimiter join — not safe for arbitrary strings)

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Codec {
    private static final String D = "|";

    public String encode(List<String> strs) {
        return String.join(D, strs);
    }

    public List<String> decode(String s) {
        if (s.isEmpty()) {
            return new ArrayList<>();
        }
        return new ArrayList<>(Arrays.asList(s.split("\\|", -1)));
    }
}

Why this is “brute” / wrong for LC 271: If a string contains |, split creates too many pieces—data loss. Also encode([""]) becomes "", which decode treats as an empty list—another failure. Length-prefix fixes both cases.

Time: O(total chars) for join/split.
Space: O(total chars) for the joined string and list.

Optimal

import java.util.ArrayList;
import java.util.List;

public class Codec {

    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();
        for (String x : strs) {
            sb.append(x.length());
            sb.append('#');
            sb.append(x);
        }
        return sb.toString();
    }

    public List<String> decode(String s) {
        List<String> out = new ArrayList<>();
        int i = 0;
        while (i < s.length()) {
            int j = i;
            while (Character.isDigit(s.charAt(j))) {
                j++;
            }
            int len = Integer.parseInt(s.substring(i, j));
            j++; // skip '#'
            out.add(s.substring(j, j + len));
            i = j + len;
        }
        return out;
    }
}

Time: O(n) over total characters.
Space: O(n) for output list and encoded string.

---

5. The “Java vs. Others” Edge

• substring indices substring(begin, end) is end-exclusive; off-by-one bugs break decoding.
• Digit parsing Lengths fit in int for LeetCode; for extreme sizes use long or streaming.
• Unicode Java String length is UTF-16 code units, not grapheme clusters—same as most LeetCode string problems.
• Python Often uses str(len) + a delimiter similarly; Java’s StringBuilder mirrors ''.join patterns but mutable.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute (escape delimiters)	O(n)	O(n)	Tricky corner cases; not recommended.
Length-prefix	O(n)	O(n)	Robust for arbitrary characters; standard answer.