Encode and Decode Strings

MediumStrings · Serialization🧩 String Manipulation LeetCode #271 ↗Updated Oct 30, 2026

Problem

Design a Codec with two methods: encode turns a List<String> into one string, and decode turns that string back into the exact same list (same order, same contents, empty strings included). The strings may contain any ASCII character, including whatever you might want to use as a separator. Keep no state between calls.

Input["lint","code","love","you"]Output["lint","code","love","you"]

Input["a#b","","3#x"]Output["a#b","","3#x"]

1 ≤ strs.length ≤ 200 · 0 ≤ strs[i].length ≤ 200 · any of the 256 ASCII chars · Follow-up: make it work for any character set.

Try it yourself

Java

class Codec {
    public String encode(List<String> strs) {
        
    }

    public List<String> decode(String s) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Any separator character can also appear inside the data. Instead of searching for where a string ends, announce its length up front (len#text): the decoder then jumps over the text without reading it.

PatternString Manipulation

Instinct Reading, comparing or rebuilding text character by character? Walk indices on a char[] and build output with a StringBuilder, never with + in a loop.

Memory hack Chars in an array, pointers on the ends, builder at the back - strings are just arrays wearing a costume.

Open the String Manipulation guide →

Approaches

Brute ForceOut-of-Range Sentinel

Time O(n)Space O(n)

Inputs only use chars 0–255, so a char like (char) 257 can never occur in the data. Append it after every string as a terminator and split on it when decoding. A terminator (not a joiner) keeps [] and [""] distinct.

Java

class Codec {
    private static final char END = (char) 257; // never appears in ASCII input

    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();
        for (String s : strs) {
            sb.append(s).append(END);
        }
        return sb.toString();
    }

    public List<String> decode(String s) {
        List<String> out = new ArrayList<>();
        int start = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == END) {
                out.add(s.substring(start, i));
                start = i + 1;
            }
        }
        return out;
    }
}

Tiny, but correct only because of the ASCII constraint — fails the follow-up.

BetterEscape Character + Terminator

Time O(n)Space O(n)

Pick / as an escape: a literal / is written as // and each string ends with /e. While decoding, a / always starts a two-char code, so a real slash and a terminator can never be confused — works for any alphabet.

Java

class Codec {
    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();
        for (String s : strs) {
            for (char c : s.toCharArray()) {
                if (c == '/') sb.append("//"); // escape the escape char
                else sb.append(c);
            }
            sb.append("/e"); // end of one string
        }
        return sb.toString();
    }

    public List<String> decode(String s) {
        List<String> out = new ArrayList<>();
        StringBuilder cur = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c != '/') {
                cur.append(c);
            } else if (s.charAt(++i) == 'e') { // read the code after '/'
                out.add(cur.toString());
                cur.setLength(0);
            } else {
                cur.append('/');
            }
        }
        return out;
    }
}

Fully general, but decoding must inspect every char and output can double in size.

OptimalLength Prefix (`len#text`)

Time O(n)Space O(n)

Write each string as its length, a #, then the raw text. The decoder reads digits up to the first #, then copies exactly len chars without looking at them — so # or digits inside the text are harmless.

Java

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

    public List<String> decode(String s) {
        List<String> out = new ArrayList<>();
        int i = 0;
        while (i < s.length()) {
            int hash = s.indexOf('#', i); // header is digits only, so first '#' ends it
            int len = Integer.parseInt(s.substring(i, hash));
            int start = hash + 1;
            out.add(s.substring(start, start + len));
            i = start + len; // jump past the payload
        }
        return out;
    }
}

Any character set, tiny overhead, and the payload is never scanned — the standard answer.

Pro tip

A fixed-width header (e.g. 4 chars or 4 bytes for the length) removes the # entirely — the same idea network protocols use.

At a glance

Level	Approach	Time	Space
Brute Force	Out-of-Range Sentinel	`O(n)`	`O(n)`
Better	Escape Character + Terminator	`O(n)`	`O(n)`
Optimal	Length Prefix (`len#text`)	`O(n)`	`O(n)`

Common pitfalls

Joining with a plain separator like , or # — breaks as soon as the data contains it.
Using a joiner instead of a terminator — [] and [""] both encode to "".
In the length-prefix decoder, searching for # from the start of the payload instead of the header.

Interview tips

Start by asking what characters can appear; it shows why naive delimiters fail.
Test with tricky data: empty strings, strings that look like headers (3#x), an empty list.
Mention that this is how HTTP Content-Length and many binary formats frame messages.

Pattern

Length-prefixed framing → serialize variable-length items into one stream when no safe delimiter exists.

My notes saved in this browser