20 · String Parsing & Expression Evaluation
#271 Encode and Decode Strings
the problem
In plain words
Design a Codec with encode(List<String> strs), which packs a list of strings into one String, and decode(String s), which unpacks it into the same list. The packed String may be decoded by a different Codec object, so it must carry everything. The strings can contain any of the 256 ASCII characters — including whatever separator you pick. Don't use a ready-made serializer.
in strs = ["Hello","World"]
out ["Hello","World"]
One valid encoding: "5#Hello5#World".
in strs = [""]
out [""]
One empty string must come back as one empty string, not as an empty list.
- 1 ≤ strs.length ≤ 200
- 0 ≤ strs[i].length ≤ 200
- strs[i] may contain any of the 256 ASCII characters
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code right here. Stuck for 20 minutes? Open one hint at a time.
This one is LeetCode Premium. You don't need a subscription: solve it right here. The free alternative linked above is the closest free practice; its label says how close it is.
Solve it in the browser
Design: implement every operation. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternString parsing
where this runsProtocol Buffers store every string field as a varint length followed by the bytes (the LEN wire type) — the same idea in binary.
Any separator can also appear inside the data. So write each string's length in front of it: the reader takes exactly that many characters without looking at them.
solutions
From brute force to optimal
Double every real '#' to "##" and end each string with "#;". A single '#' followed by ';' can only be an end marker.
- encode: for each char, '#' → "##"; after each string append "#;".
- decode: "##" → '#'; "#;" → finish the current string; other chars append.
N = total characters; every character is read and written a constant number of times.
The encoded String (up to about twice as long) and the output list.
class Codec { /** Every '#' inside a string is doubled to "##"; "#;" ends each string. ["a#", "b"] → "a###;b#;". */ public String encode(List<String> strs) { StringBuilder sb = new StringBuilder(); for (String s : strs) { for (char c : s.toCharArray()) { if (c == '#') sb.append('#'); // escape: a real '#' is written twice sb.append(c); } sb.append("#;"); // a lone '#' followed by ';' can only be the end } 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 + 1) == '#') { // "##" → one real '#' cur.append('#'); i++; } else { // "#;" → the string is complete out.add(cur.toString()); cur.setLength(0); i++; } } return out; }}Write each string as its length, a '#', then the string unchanged. Decode reads the digits up to '#', then takes exactly that many characters.
- encode: for each s, append s.length() + "#" + s.
- decode: i = 0; hash = s.indexOf('#', i); len = parseInt(s.substring(i, hash)).
- Take s.substring(hash + 1, hash + 1 + len); i = hash + 1 + len; repeat.
Headers are scanned, payloads are copied once without inspection.
The encoded String and the output list; headers add at most 4 chars per string here.
class Codec { /** ["hi", "", "a#3"] → "2#hi0#3#a#3". Each string travels with its own length in front. */ public String encode(List<String> strs) { StringBuilder sb = new StringBuilder(); for (String s : strs) { sb.append(s.length()).append('#').append(s); // header "len#", then the raw text } return sb.toString(); } public List<String> decode(String s) { List<String> out = new ArrayList<>(); int i = 0; // always the start of a header while (i < s.length()) { int hash = s.indexOf('#', i); // a header is digits then '#': the first '#' ends it int len = Integer.parseInt(s.substring(i, hash)); out.add(s.substring(hash + 1, hash + 1 + len)); // take exactly len chars, '#' or not i = hash + 1 + len; // jump straight to the next header } return out; }}Dry run
in the room
How to say it in the interview
talk track
- Show why a plain delimiter fails: ["a,b"] and ["a", "b"] both become "a,b" with ','.
- Propose length#string and decode the example by hand.
- Explain why the first '#' after i always ends the header: a header is only digits.
- Mention that encode and decode keep no fields — a different Codec may decode.
traps
- Joining with a delimiter (',', '#', even a rare character): some input will contain it.
- Decoding with
split: it drops trailing empty strings, so ["a", ""] comes back as ["a"]. - Keeping the list in a field: a different Codec object does the decoding.
what they ask next
Follow-ups
A fixed-width header instead of len#?
Write the length as exactly 4 characters, or as one char (a Java char holds 0 to 65,535). The reader then needs no '#' at all — that's how binary protocols frame messages.
Any Unicode text, sent as bytes?
Encode each string to UTF-8 bytes and prefix the byte count, not the char count — exactly what DataOutputStream.writeUTF does with its 2-byte length.
before you submit
Edge cases to test
- Empty strings: [""] must decode to a list holding one empty string.
- Strings that look like headers: "2#hi", "#", "12#".
- All 256 ASCII characters, including control characters like newline.
practise next
Similar problems
- #297Serialize and Deserialize Binary TreeHardin Traversals
- #394Decode StringMediumin Stacks
- #8String to Integer (atoi)Mediumin Parsing