8.Encode and Decode Strings

MediumBlind 75Arrays & Hashing · 8/9

Problem

Design an algorithm that encodes a list of strings into a single string, and a matching algorithm that decodes that string back into the original list.

The strings may contain any characters — including commas, digits, #, or any delimiter you might be tempted to use — and may be empty. decode(encode(strs)) must return a list equal to strs. No serialization helpers like eval are allowed; the format is yours to design.

Examples

Input:  ["neet", "code", "love", "you"]
Output: ["neet", "code", "love", "you"]
Explanation: encode produces one string (e.g. "4#neet4#code4#love3#you"); decode restores the list.

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

Input:  ["", "#3", "a,b"]
Output: ["", "#3", "a,b"]
Explanation: Empty strings and strings containing the delimiter must survive the round trip.

Constraints

0 <= strs.length < 100
0 <= strs[i].length < 200
strs[i] contains any of the 256 valid ASCII characters.

💡 Key Insight

A plain delimiter fails because the delimiter itself can appear inside a string. The fix is length-prefixing: write each string as <length>#<string>. The decoder reads digits up to the first #, which gives the exact length, then copies that many characters without looking at them — so a # or digit inside the payload can never be misread as structure.

Escaped Delimiter

TimeO(m)SpaceO(m)

Intuition

Use a separator such as , between strings, and make it unambiguous by escaping: every / in a string becomes // and every , becomes /,. A lone , (not preceded by an escape) is then always a separator. To distinguish an empty list from a list holding one empty string, terminate every string with a , rather than only separating them.

Algorithm

Encode: for each string, append each character (doubling / and prefixing , with /), then append a terminating ,.
Decode: scan characters with a StringBuilder cur:
- On /, append the next character literally and skip it.
- On an unescaped ,, finish cur as one string and reset it.
- Otherwise append the character.

Visualization

strs   = ["a,b", "", "c/"]
encode → "a/,b,,c//,"

decode segments:
  a / , b ,   → "/," is an escaped comma, then "," ends → "a,b"
  ,           → ends immediately                        → ""
  c / / ,     → "//" is an escaped slash, then "," ends → "c/"

Code

java

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

class Solution {
    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();
        for (String s : strs) {
            for (char ch : s.toCharArray()) {
                if (ch == '/' || ch == ',') {
                    sb.append('/'); // escape the escape char and the separator
                }
                sb.append(ch);
            }
            sb.append(','); // terminator after every string (handles empty strings)
        }
        return sb.toString();
    }

    public List<String> decode(String str) {
        List<String> result = new ArrayList<>();
        StringBuilder cur = new StringBuilder();
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            if (ch == '/') {
                cur.append(str.charAt(i + 1)); // take the escaped char literally
                i++;
            } else if (ch == ',') {
                result.add(cur.toString()); // unescaped comma ends a string
                cur.setLength(0);
            } else {
                cur.append(ch);
            }
        }
        return result;
    }
}

Complexity

Time: O(m) — m is the total number of characters; each is processed a constant number of times.
Space: O(m) — the encoded string can be up to twice the input size in the worst case (all escapes).

Length PrefixOptimal

TimeO(m)SpaceO(m)

Intuition

Prefix every string with its length and a #: "neet" becomes "4#neet". When decoding at position i, read digits until the # to learn the length len, then the payload is exactly str.substring(j + 1, j + 1 + len). We jump over the payload instead of scanning it, so its contents never matter. Unlike escaping, the encoding adds only a few bytes per string.

Algorithm

Encode: for each s, append s.length(), then #, then s.
Decode: i = 0; while i < str.length():
- j = i; advance j until str.charAt(j) == '#'.
- len = parseInt(str.substring(i, j)).
- Add str.substring(j + 1, j + 1 + len) to the result.
- i = j + 1 + len.

Dry Run

flowchart TD
    A["encoded = 4#neet2#3#0#"] --> B["i=0: digits '4' until '#' at j=1<br/>take 4 chars: neet"]
    B --> C["i=6: digits '2' until '#' at j=7<br/>take 2 chars: 3#"]
    C --> D["i=10: digits '0' until '#' at j=11<br/>take 0 chars: empty string"]
    D --> E["i=12 = length: stop"]
    E --> F["result = [neet, 3#, empty]"]

Code

java

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

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

    public List<String> decode(String str) {
        List<String> result = new ArrayList<>();
        int i = 0;
        while (i < str.length()) {
            int j = i;
            while (str.charAt(j) != '#') { // the length header contains only digits
                j++;
            }
            int len = Integer.parseInt(str.substring(i, j));
            int start = j + 1;
            result.add(str.substring(start, start + len)); // payload is copied blindly
            i = start + len; // jump to the next header
        }
        return result;
    }
}

Complexity

Time: O(m) — every character of the encoded string is read once (headers scanned, payloads copied).
Space: O(m) — the encoded string / decoded list; overhead is O(log L + 1) per string for the header.

Complexity Comparison

Approach	Time	Space
Escaped Delimiter	O(m)	O(m), up to 2× expansion
Length Prefix	O(m)	O(m), small header per string

Common Pitfalls

Using a bare delimiter (e.g. joining with , or #) — breaks as soon as a string contains that character.
Searching for the # with indexOf('#') from the wrong start index, or scanning inside the payload for structure; the payload of "3#" contains a #.
Forgetting empty strings: [""] must encode to something non-empty ("0#"), otherwise it is indistinguishable from [].
Assuming the length is a single digit — lengths up to 199 need multi-digit parsing.