Encode and Decode Strings

MediumArrays & HashingArrayStringDesign

Problem

Design two functions: one that packs a list of strings into a single string, and one that recovers the original list from that packed string, in order. The strings may contain any characters at all, including whatever character might otherwise be used as a separator.

Example. Encoding ["ab", "c"] and then decoding must return exactly ["ab", "c"], and this must hold even if one of the input strings itself contains the delimiter the encoder uses internally.

Key idea

The obvious approach joins the strings with a common separator, like a comma. That breaks the moment a string contains a comma itself, since decoding cannot tell whether a given comma is a separator or a literal character. A rarer separator only lowers the odds of collision; it does not remove the ambiguity.

The robust technique is length-prefixing: before each string, write its length as digits, then a marker character that can never appear inside a length field, then the raw string itself. Because digits never include the marker, a decoder reads characters up to the next marker, parses them as a number, and knows exactly how many raw characters to consume next, regardless of their content. After consuming that many characters, it moves to the next length field and repeats.

Solution

class Codec {
  encode(strs: string[]): string {
    let encoded = '';
    for (const str of strs) {
      encoded += `${str.length}#${str}`; // length, then marker, then the raw string
    }
    return encoded;
  }

  decode(s: string): string[] {
    const result: string[] = [];
    let i = 0;

    while (i < s.length) {
      let j = i;
      while (s[j] !== '#') {
        j++; // scan to the marker that ends the length field
      }
      const length = Number(s.slice(i, j));
      const start = j + 1;
      result.push(s.slice(start, start + length)); // consume exactly `length` raw characters
      i = start + length;
    }

    return result;
  }
}

Complexity

  • Time: O(total length of all strings). Every character is read or written exactly once during encoding and decoding.
  • Space: O(total length of all strings). The encoded string and the reconstructed list are each proportional to the input size.

Watch out for

  • The length field must be self-delimiting: read digits until a non-digit marker, then consume exactly that many raw characters no matter their content.
  • Do not escape the delimiter inside strings; length-prefixing removes the need for escaping entirely.
  • An empty string simply encodes as a zero length, the marker, and nothing else.

Pattern

This is the length-prefixed, self-delimiting encoding pattern behind many real network protocols and serialization formats. It applies whenever data of unknown content must be split out of a single stream without relying on a reserved character.

Related questions