Encode and Decode Strings

Problem in Plain English

Pack a list of strings into one string, then recover the same strings in the same order. Length fields preserve empty strings and characters that could otherwise be mistaken for separators.

Problem Statement

Implement encode(strs) to produce one string and decode(encoded) to recover the original list, including its order, empty strings, and every character. The encoded representation is your choice; the output shown in the examples is the decoded list.

Do not delegate the task to a built-in serialization method such as eval. The decoder receives valid output from the matching encoder, so malformed-message validation is outside this exercise. The sender and receiver must work independently; do not keep the original list in shared state.

Constraints

0 <= strs.length < 100
0 <= strs[i].length < 200
Strings may contain any of the 256 character values specified by this question, including separators and control characters.
Lengths and slices must use the same unit. These implementations round-trip within each language; arbitrary Unicode exchanged across languages needs an agreed byte encoding and byte lengths.

Examples

Example 1

Input: strs = ["lint", "code", "love", "you"]
Output: ["lint", "code", "love", "you"]

One valid encoding is 4#lint4#code4#love3#you, which decodes back to the original list.

Example 2

Input: strs = ["we", "say", ":", "yes"]
Output: ["we", "say", ":", "yes"]

The format must survive : inside a string, so bare joining on a delimiter character is not enough.

Example 3

Input: strs = ["", "a#b", "12|,:"]
Output: ["", "a#b", "12|,:"]

The chunk encoding is 0#3#a#b5#12|,:. After reading each length, the decoder consumes exactly that many characters, preserving the empty first string, the embedded #, and the punctuation.

Example 4

Input: strs = []
Output: []

Both approaches encode an empty list as an empty string. A list containing one empty string has a length field, so it remains distinguishable.

Intuition

A separator alone cannot tell data from boundaries: joining ["a#b", "c"] with # looks like three strings. Send the size as well. In Example 1, 4#lint means read the length 4 up to #, then take exactly four characters. Any # inside those four characters is data. Zero is a useful length too: 0# preserves one empty string, while no chunks represents an empty list.

Approaches

Length Header

Solution Details

Reveal Length Header: intuition, complexity, and code

Intuition

Send all lengths in a header, then concatenate the strings as raw data. This separates the boundary information from the payload, but the decoder must read the full header before extracting the first string.

Step-by-Step Logic

For an empty list return an empty encoding; decoding it returns []. Otherwise collect each string length in order. Example 1 gives [4, 4, 4, 3].
Join decimal lengths with commas and end the header with |. Append all raw strings: 4,4,4,3|lintcodeloveyou.
Decode by locating only the first |. The header contains digits and commas, so this marker ends the header even when the payload contains more pipes. The first payload index is 8.
For every length, extract that many characters at the current cursor and advance it by the length. Example 1 takes slices [8,12), [12,16), [16,20), and [20,23). A zero length produces an empty string.
Return ["lint", "code", "love", "you"]. Only the encoding is needed by the decoder; no sender state is shared.

Why It Works

The header has exactly one length per input string, in the original order. Its first pipe has a unique role because the header itself contains only digits and commas. Starting just after that pipe, consuming each stored length partitions the payload into the same original strings. Zero lengths retain empty entries, and payload delimiters never affect the header parsing.

Dry Run

Length Header: variable states at each step
Phase	Action or length	Cursor or accumulated encoding	Decoded list
Encode	Collect all lengths	`4,4,4,3`	not decoding
Encode	Append marker and payload	`4,4,4,3` + pipe + `lintcodeloveyou`	not decoding
Decode	First pipe is at `7`	start `8`	`[]`
Decode	`4`: slice `[8,12)`	next `12`	`["lint"]`
Decode	`4`: slice `[12,16)`	next `16`	`["lint", "code"]`
Decode	`4`: slice `[16,20)`	next `20`	`["lint", "code", "love"]`
Decode	`3`: slice `[20,23)`	end `23`	`["lint", "code", "love", "you"]`

Complexity Analysis

Time Complexity

O(L + k)

Space Complexity

O(L + k)

Let k be the number of strings and L their total length. Under the bounded string lengths, each length field has constant size. Encoding copies L payload characters and writes k lengths; decoding scans the header and copies L characters into k strings. Both calls take O(L + k) time and O(L + k) space including returned data. The separate header and lengths array also require O(k) metadata storage; L alone misses a list of empty strings.

Code

Solution.java

1import java.util.List;2import java.util.ArrayList;3
4class Solution {5    public String encode(List<String> strs) {6        if (strs.isEmpty()) {7            return "";8        }9        StringBuilder header = new StringBuilder();10        StringBuilder data = new StringBuilder();11        for (int i = 0; i < strs.size(); i++) {12            header.append(strs.get(i).length());13            if (i < strs.size() - 1) {14                header.append(",");15            }16            data.append(strs.get(i));17        }18        return header.toString() + "|" + data.toString();19    }20    public List<String> decode(String s) {21        if (s.isEmpty()) {22            return new ArrayList<>();23        }24        int split = s.indexOf('|');25        String[] lengths = s.substring(0, split).split(",");26        List<String> res = new ArrayList<>();27        int i = split + 1;28        for (String part : lengths) {29            int len = Integer.parseInt(part);30            res.add(s.substring(i, i + len));31            i += len;32        }33        return res;34    }35}

Hints

Hint 1

Joining with a plain delimiter breaks as soon as a string contains that same character, so the format must carry more information.

Hint 2

A length placed before each string tells the decoder exactly how many characters belong to it.

Hint 3

Read digits up to a marker to get the length, slice that many characters, and repeat from the new cursor.

Edge Cases

Empty list [] encodes as an empty string. One empty string [""] encodes as 0| with the header approach or 0# with chunks; neither is an empty list.
Repeated empty strings ["", "", ""] must preserve three entries; zero-length slices do not mean the decoder should stop.
Digits and markers are data after the header: ["123", "#", "|", ","] round-trips unchanged. Multi-digit lengths must be read up to the marker, not as one digit.
Null characters, newlines, spaces, and all 256 allowed character values must survive; never trim or split the payload.
The maximum allowed count is 99 and maximum string length is 199. These bounds do not remove the need for multi-digit length fields.
Follow-up: Java and JavaScript measure UTF-16 code units while Python counts Unicode code points. Same-language round trips work, but interoperability requires matching units, such as UTF-8 byte lengths and byte slicing.

Common Mistakes and Interview Tips

Using split on the entire encoding destroys payloads containing the marker. Scan only the length header, then slice a counted payload.
Forgetting the marker when moving the cursor: the next start is j + 1 + length, even when length is zero.
Treating empty encoding as one empty string loses the distinction between [] and [""].
Repeatedly appending to immutable strings can copy earlier output many times. Use StringBuilder in Java and chunk arrays with join in Python and JavaScript.
Interview tip: demonstrate ["", "a#b"] and explain why the embedded marker is never interpreted. Both approaches are linear; chunk prefixes are marked optimal for their simpler incremental decoding, rather than an asymptotic improvement.
This parser assumes valid encoder output. For an untrusted network message, separately validate numeric headers, payload bounds, and limits before slicing.

Key Takeaway

When arbitrary data can contain a separator, length framing separates boundary information from contents. Read a header, then consume exactly the declared amount; always agree on whether length counts characters, code units, or bytes.