271. Encode and Decode Strings

Most problems in the arrays and hashing set are frequency-map puzzles. This one isn’t — it’s a tiny serialization design question, and the whole thing hinges on one insight about why the obvious answer breaks. Get that insight and the code writes itself in a few lines.

The problem

You’re handed a list of strings and asked to flatten it into a single string that can travel over a network, then reconstruct the exact original list on the other end. The catch: a string can contain any character, so nothing is off-limits as content. (Full statement on LeetCode.)

Take ["cat", "", "a#b"]. It has an empty string in the middle and a literal # inside the last element — both are the kinds of cases a naive encoder quietly corrupts.

Intuition: a delimiter can’t work, a length prefix can

The first idea everyone reaches for is to glue the strings together with a separator, say cat##a#b, and split on # to decode. It falls apart immediately: the # inside "a#b" is indistinguishable from the # you inserted, so decode has no way to know which is which. Pick a fancier delimiter and you’ve only moved the problem — the spec says strings can contain any character, so every possible delimiter can also appear as data.

The fix is to stop treating the boundary as a special character and treat it as a count instead. Before each string, write down its length and a marker:

$\texttt{<length>} \; \texttt{\#} \; \texttt{<string>}$

Now decode never has to guess. It reads digits up to the first #, parses them as a number $k$, then grabs exactly the next $k$ characters as the payload — no matter what those characters are. The # inside the data is harmless because we never search for it in the payload; we jump straight past it by count. "a#b" becomes 3#a#b, and decode reads “length 3, take three chars” and lands on a#b intact. An empty string is just 0#, which is why the length prefix handles it for free where a delimiter approach would drop it.

Solution

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

public class Codec {

    // Encode: prefix every string with its length and a '#' marker.
    // Format per item: "<len>#<string>"  ->  "cat" becomes "3#cat".
    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();
        for (String s : strs) {
            sb.append(s.length()).append('#').append(s);
        }
        return sb.toString();
    }

    // Decode: read the length, skip the '#', then slice exactly that many chars.
    public List<String> decode(String s) {
        List<String> result = new ArrayList<>();
        int i = 0;
        while (i < s.length()) {
            int j = i;
            while (s.charAt(j) != '#') { // the first '#' ends the length field
                j++;
            }
            int len = Integer.parseInt(s.substring(i, j));
            String word = s.substring(j + 1, j + 1 + len); // count, not search
            result.add(word);
            i = j + 1 + len; // jump to the next length field
        }
        return result;
    }
}

The only pointer arithmetic to keep straight is the last line: after the # at index j, the payload spans len characters, so the next record starts at j + 1 + len.

Complexity

Let $n$ be the total number of characters across every string and $m$ the number of strings.

Operation	Time	Space
encode	$O(n + m)$	$O(n + m)$
decode	$O(n + m)$	$O(n + m)$

Each character is appended once and read once. The $m$ term matters because the length prefix and # marker cost a bit of work per string regardless of content — a list of many empty strings has $n = 0$ but still takes time and space linear in $m$.

In an interview

Lead with why the naive delimiter fails — that’s the whole point of the question, and saying “any delimiter can appear inside the data, so I’ll length-prefix instead” shows you saw the trap before writing code. Then name the two edge cases interviewers poke at: an empty input list (encode returns "", decode’s loop never runs, you get an empty list back) and an empty string element (encoded as 0#, decoded correctly), since a split-on-delimiter solution mishandles both.

This one sits a little apart from its group-mates in the arrays and hashing pattern: where Group Anagrams and Top K Frequent Elements lean on a hash map to bucket or count, here the “map” is really just the self-describing wire format. Recognizing that a problem is about encoding state into the data itself rather than tallying it is a useful thing to have in your back pocket.

References

• LeetCode 271 — Encode and Decode Strings