☕ DSA Java Articles

Topics › Strings › Medium String Problems

Encode and Decode Strings

Medium TUF ID 331 Blind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Design two functions. encode takes a list of strings and returns a single string. decode takes that single string and must return the original list, exactly. Think of it as sending a list over a channel that can only carry one string.

The strings may contain any character, including whatever symbol you might like to use as a separator, and they may be empty. You may not use a library serializer; the point is to design the format yourself.

Constraints (LeetCode 271): up to 200 strings, each of length 0 to 200, made of any of the 256 ASCII characters. The Java methods work for any Java String, and for an empty list.

Example 1

strs = ["lint", "code", "love", "you"]
decode(encode(strs)) = ["lint", "code", "love", "you"]

Example 2

strs = ["#", "", "3#ab"]
decode(encode(strs)) = ["#", "", "3#ab"]   // separators, an empty string and a fake header must all survive

Why a plain separator does not work

The first idea is to join the strings with a separator, say ",", and split on it when decoding. It breaks as soon as a string contains a comma: ["a,b"] and ["a", "b"] both encode to "a,b". Picking a rarer separator does not help, because the input may contain any character. The format has to stay unambiguous whatever the strings contain.

There are two further traps. Java’s String.split silently drops trailing empty strings, so ["a", ""] would come back as ["a"]. And the empty list [] and the list holding one empty string [""] must encode differently, which a plain join cannot do (both give "").

So we need a format where a decoder can always tell data characters apart from structure. There are two standard ways: escape the separator inside the data, or announce the length of each string before it.

Approach 1: Escaping

Intuition. Reserve one character, '#', as a control character, and make sure a '#' in the data never looks like structure. Inside a word, write every '#' twice: "##" means “a literal #”. At the end of each word, write "#;": a '#' followed by anything other than another '#' means “this word is over”.

Why can the decoder never be confused? Read the encoding left to right. Every '#' in it was written either as the first half of "##" or as the first half of "#;". So whenever the decoder sees a '#', the very next character says which one it is, and the decoder then skips both. Any character that is not '#' is plain data. The same characters that the encoder grouped into tokens are exactly the ones the decoder groups, so the round trip is exact.

Algorithm (encode).

  1. For each word, copy its characters, writing "##" for every '#'.
  2. Append "#;" after each word.

Algorithm (decode).

  1. Scan with index i, building the current word.
  2. If s[i] is not '#', append it and move one step.
  3. If s[i..i+1] is "##", append one '#' and move two steps.
  4. Otherwise ("#;"), close the current word, add it to the result, and move two steps.
static String encodeEscaped(List<String> strs) {
    StringBuilder sb = new StringBuilder();
    for (String s : strs) {
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '#') sb.append("##");          // escaped '#'
            else sb.append(c);
        }
        sb.append("#;");                            // '#' followed by anything except '#' ends a word
    }
    return sb.toString();
}

static List<String> decodeEscaped(String s) {
    List<String> out = new ArrayList<>();
    StringBuilder cur = new StringBuilder();
    int i = 0;
    while (i < s.length()) {
        char c = s.charAt(i);
        if (c != '#') {
            cur.append(c);
            i++;
        } else if (s.charAt(i + 1) == '#') {        // a '#' is never the last character of a valid encoding
            cur.append('#');
            i += 2;
        } else {
            out.add(cur.toString());
            cur.setLength(0);
            i += 2;
        }
    }
    return out;
}

Complexity. Time O(L) for both functions, where L is the total number of characters. Space O(L) for the output. In the worst case (every character is '#') the encoding is twice as long as the data.

The empty list encodes to "", while [""] encodes to "#;", so the two are distinguished. Escaping is how CSV quotes, JSON strings and C string literals work, so it is worth understanding even though the next approach is simpler here.

Approach 2: Optimal, length prefix

Intuition. Instead of marking where a word ends, say up front how long it is. Write each word as length + '#' + word. The decoder reads the digits up to the first '#', learns the length len, and then copies the next len characters without looking at them. Because it never inspects the payload, the payload may contain '#', digits, or anything else.

The '#' after the length is still necessary, because lengths have different numbers of digits. Without it, "12abc" could mean a 1-character word "2" followed by garbage, or a 12-character word. The header contains only digits, so the first '#' after the start of a header always ends it. (An alternative is a fixed-width header, such as exactly four digits or four raw bytes, which is how many network protocols frame their messages.)

Algorithm (encode).

  1. For each word, append its length, then '#', then the word.

Algorithm (decode).

  1. Start at i = 0. While i is inside the string:
  2. Accumulate digits into len until reaching '#'; skip the '#'.
  3. Take s.substring(i, i + len) as the next word, and set i += len.
static String encode(List<String> strs) {
    StringBuilder sb = new StringBuilder();
    for (String s : strs) sb.append(s.length()).append('#').append(s);
    return sb.toString();
}

static List<String> decode(String s) {
    List<String> out = new ArrayList<>();
    int i = 0;
    while (i < s.length()) {
        int len = 0;
        while (s.charAt(i) != '#') {                // the header contains only digits
            len = len * 10 + (s.charAt(i) - '0');
            i++;
        }
        i++;                                        // skip the '#' that ends the header
        out.add(s.substring(i, i + len));           // the payload may contain '#' or digits; we never look at it
        i += len;
    }
    return out;
}

Dry run of decode("3#a#b0#"), the encoding of ["a#b", ""]:

i at header start digits read len word taken next i
0 3 3 "a#b" (the # inside is just data) 5
5 0 0 "" 7 = end

Complexity. Time O(L): every character is visited once, either as a header digit or by substring. Space O(L) for the output; the overhead is only a few header characters per word, regardless of content.

This is the answer interviewers usually expect. It is simpler than escaping, never inflates the data, and the decoder can even jump over words without reading them.

Edge cases and pitfalls