Encode and Decode Strings

Design a class Codec with two methods:

• encode(strs) turns a list of strings into one string.
• decode(s) takes a string produced by encode and returns the original list, with the same strings in the same order.

The two methods run on separate Codec instances, so decode only ever sees the encoded string; nothing may be stored on the object between calls. The strings may contain any characters, including digits, punctuation, whitespace, newlines and non-Latin letters or emoji, and some may be empty. Design the format yourself instead of calling a ready-made serializer such as JSON.

The judge passes each test list to encode, feeds the result to decode, and checks that the original list comes back.

Example 1

Example 2

Example 3

Constraints

• 0 <= strs.length <= 2000
• 0 <= strs[i].length <= 200
• strs[i] may contain any characters, including the ones your format uses as separators.

Pattern Path · Design · problem 166 of 169

Start simple

Joining with a rare delimiter (or escaping it) seems simple, but delimiters break on adversarial input and escaping needs careful two-way handling; any correct format still costs O(total length).

The key idea

The core difficulty is that any character you choose as a separator might also appear inside the data. So stop relying on separators to say where a string ends. Put the length in front of each string instead: "ab#c" becomes "4#ab#c".

Decoding is then a simple cursor walk. From position i, read digits up to the next "#"; that gives the length L. The string is the next L characters after the "#", whatever they are. Jump past them and repeat until the input is used up.

Why this cannot be fooled: the decoder only looks for "#" while reading a length, and a length consists only of digits written by the encoder. Once it knows L it never inspects the string's characters, so "#", digits or newlines inside the data are harmless. Empty strings work too ("0#"), and an empty list encodes to an empty string.

Both directions touch every character a constant number of times, so they run in time linear in the total length.

Complexity

• Time: O(total characters)
• Space: O(total characters)

Python

class Codec:
    def encode(self, strs):
        # Prefix every string with its length and a '#', e.g. "ab#c" -> "4#ab#c".
        return ''.join(f'{len(s)}#{s}' for s in strs)

    def decode(self, s):
        result = []
        i = 0
        while i < len(s):
            sep = s.index('#', i)          # the length's digits end at the first '#'
            length = int(s[i:sep])
            start = sep + 1
            result.append(s[start:start + length])  # take exactly `length` characters
            i = start + length
        return result

JavaScript

class Codec {
  encode(strs) {
    // Prefix every string with its length and a '#', e.g. "ab#c" -> "4#ab#c".
    return strs.map(s => s.length + '#' + s).join('');
  }

  decode(s) {
    const result = [];
    let i = 0;
    while (i < s.length) {
      const sep = s.indexOf('#', i);           // the length's digits end at the first '#'
      const length = Number(s.slice(i, sep));
      const start = sep + 1;
      result.push(s.slice(start, start + length)); // take exactly `length` characters
      i = start + length;
    }
    return result;
  }
}

What the interviewer is checking

The interviewer is checking whether you design a format that is unambiguous for every possible input rather than one that works on friendly examples, and whether you can argue why it is correct.

Mistakes to avoid

• Using a delimiter that can also appear in the data, so a string like "a,b" splits in two.
• Losing empty strings, or confusing an empty list with a list holding one empty string.
• Searching for the separator inside the payload instead of skipping exactly L characters.
• Building the result with repeated string concatenation in a loop, which can be quadratic in some languages.

Follow-ups to expect

• How would you support nested lists? (Prefix each element with a type tag.)
• How could you shrink the encoding? (Fixed-width binary or varint lengths.)
• How does escaping compare? (Works, but decoding is trickier.)

In real software

Length-prefixed framing is how network protocols like HTTP/2, Redis' RESP and Protocol Buffers separate messages and fields, because a length header lets binary payloads contain any bytes.

Practice next