Encode and Decode Strings (LC 271): Length Prefixing

Design encode and decode functions that pack a list of strings into one string and recover it exactly, even when the strings contain the delimiter. Escaping or length-prefixing (len#text) both run in O(N) time.

Language Selection

Choose your preferred programming language

Showing: Python

Encode and Decode Strings

Problem Statement

Write a codec with two operations:

  • encode takes a list of strings and returns a single string.
  • decode takes a string produced by encode and returns the original list.

The two sides may run on different machines, so decode only sees the encoded string. It must return exactly the same list: the same number of strings, in the same order, with the same characters. The strings may contain any of the 256 ASCII characters, including whatever character you were hoping to use as a separator, and some of them may be empty. You may not rely on library serializers such as eval or JSON; build the format yourself.

Examples

Example 1:

Input: strs = ["cat", "dog", "fish"]
Output: ["cat", "dog", "fish"]
Explanation: One valid encoding is "3#cat3#dog4#fish". Each word is stored as its length,
a '#', then its characters, so decode knows exactly where each word ends.

Example 2:

Input: strs = ["4#x", "", "#"]
Output: ["4#x", "", "#"]
Explanation: The strings contain digits and '#' and one is empty. With length prefixes the
encoding is "3#4#x0#1##". Decode reads "3", takes the next 3 characters "4#x" without looking
inside them, then reads "0" (an empty string), then "1" followed by the single character "#".

Example 3:

Input: strs = [""]
Output: [""]
Explanation: A list holding one empty string must not decode to an empty list. Its encoding is "0#".

Constraints

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] may contain any of the 256 ASCII characters.

Approach 1: Delimiter with Escaping

Algorithm

Joining with a plain separator fails as soon as a string contains that separator. The fix used by CSV files and string literals is escaping: pick an escape character, here /, and make sure that inside the encoded data a / is always followed by a second character that says what it means.

  • A literal / in the data is written as //.
  • The end of each string is written as /:.

Every string, including the last one, ends with /:, so an empty string becomes just /: and the list [""] encodes differently from an empty list.

  1. Encode: for each string, append it with every / doubled, then append /:.
  2. Decode: scan left to right with a buffer for the current string.
    • A character other than / goes into the buffer.
    • A / is always followed by one more character. If that is /, add one / to the buffer. If it is :, the current string is finished: add the buffer to the result and clear it. Skip both characters.

Implementation

Python:

from typing import List


class Codec:
    def encode(self, strs: List[str]) -> str:
        """Encodes a list of strings to a single string."""
        # Double every '/', then end each string with "/:"
        return "".join(s.replace("/", "//") + "/:" for s in strs)

    def decode(self, s: str) -> List[str]:
        """Decodes a single string to a list of strings."""
        result = []
        current = []
        i = 0
        while i < len(s):
            if s[i] == "/":
                # An escape is always two characters: "//" or "/:"
                if s[i + 1] == "/":
                    current.append("/")
                else:
                    result.append("".join(current))
                    current = []
                i += 2
            else:
                current.append(s[i])
                i += 1
        return result

Java:

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

public class Codec {

    // Encodes a list of strings to a single string.
    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();
        for (String str : strs) {
            // Double every '/', then end each string with "/:"
            sb.append(str.replace("/", "//")).append("/:");
        }
        return sb.toString();
    }

    // Decodes a single string to a list of strings.
    public List<String> decode(String s) {
        List<String> result = new ArrayList<>();
        StringBuilder current = new StringBuilder();
        int i = 0;
        while (i < s.length()) {
            char c = s.charAt(i);
            if (c == '/') {
                // An escape is always two characters: "//" or "/:"
                if (s.charAt(i + 1) == '/') {
                    current.append('/');
                } else {
                    result.add(current.toString());
                    current.setLength(0);
                }
                i += 2;
            } else {
                current.append(c);
                i++;
            }
        }
        return result;
    }
}

Go:

import "strings"

type Codec struct {
}

// Encodes a list of strings to a single string.
func (codec *Codec) Encode(strs []string) string {
    var sb strings.Builder
    for _, str := range strs {
        // Double every '/', then end each string with "/:"
        sb.WriteString(strings.ReplaceAll(str, "/", "//"))
        sb.WriteString("/:")
    }
    return sb.String()
}

// Decodes a single string to a list of strings.
func (codec *Codec) Decode(s string) []string {
    result := []string{}
    var current strings.Builder
    for i := 0; i < len(s); {
        if s[i] == '/' {
            // An escape is always two bytes: "//" or "/:"
            if s[i+1] == '/' {
                current.WriteByte('/')
            } else {
                result = append(result, current.String())
                current.Reset()
            }
            i += 2
        } else {
            current.WriteByte(s[i])
            i++
        }
    }
    return result
}

JavaScript:

/**
 * Encodes a list of strings to a single string.
 *
 * @param {string[]} strs
 * @return {string}
 */
var encode = function(strs) {
    // Double every '/', then end each string with "/:"
    return strs.map(str => str.replaceAll('/', '//') + '/:').join('');
};

/**
 * Decodes a single string to a list of strings.
 *
 * @param {string} s
 * @return {string[]}
 */
var decode = function(s) {
    const result = [];
    let current = [];
    let i = 0;
    while (i < s.length) {
        if (s[i] === '/') {
            // An escape is always two characters: "//" or "/:"
            if (s[i + 1] === '/') {
                current.push('/');
            } else {
                result.push(current.join(''));
                current = [];
            }
            i += 2;
        } else {
            current.push(s[i]);
            i++;
        }
    }
    return result;
};

C#:

using System.Collections.Generic;
using System.Text;

public class Codec {

    // Encodes a list of strings to a single string.
    public string encode(IList<string> strs) {
        var sb = new StringBuilder();
        foreach (string str in strs) {
            // Double every '/', then end each string with "/:"
            sb.Append(str.Replace("/", "//")).Append("/:");
        }
        return sb.ToString();
    }

    // Decodes a single string to a list of strings.
    public IList<string> decode(string s) {
        var result = new List<string>();
        var current = new StringBuilder();
        int i = 0;
        while (i < s.Length) {
            if (s[i] == '/') {
                // An escape is always two characters: "//" or "/:"
                if (s[i + 1] == '/') {
                    current.Append('/');
                } else {
                    result.Add(current.ToString());
                    current.Clear();
                }
                i += 2;
            } else {
                current.Append(s[i]);
                i++;
            }
        }
        return result;
    }
}

C++:

#include <string>
#include <vector>
using namespace std;

class Codec {
public:
    // Encodes a list of strings to a single string.
    string encode(vector<string>& strs) {
        string out;
        for (const string& str : strs) {
            // Double every '/', then end each string with "/:"
            for (char c : str) {
                if (c == '/') out += '/';
                out += c;
            }
            out += "/:";
        }
        return out;
    }

    // Decodes a single string to a list of strings.
    vector<string> decode(string s) {
        vector<string> result;
        string current;
        size_t i = 0;
        while (i < s.size()) {
            if (s[i] == '/') {
                // An escape is always two characters: "//" or "/:"
                if (s[i + 1] == '/') {
                    current += '/';
                } else {
                    result.push_back(current);
                    current.clear();
                }
                i += 2;
            } else {
                current += s[i];
                i++;
            }
        }
        return result;
    }
};

Complexity Analysis

  • Time: O(N), where N is the total number of characters across all strings. Encoding and decoding each touch every character a constant number of times.
  • Space: O(N + k) for the encoded string, where k is the number of strings: in the worst case (every character a /) the output is 2N + 2k characters. Decoding needs O(N) for the result list.

Approach 2: Length Prefixing (Optimal)

Algorithm

Escaping makes the decoder inspect every character to tell data from structure. A length prefix avoids that question: before each string, write its length in decimal followed by #. The decoder reads digits up to the first #, which is always the separator because a length contains only digits, and then copies exactly that many characters without looking at them. A #, a digit or a / inside the string is just data.

This is the same idea network protocols use when they frame messages with a length field.

  1. Encode: for each string str, append len(str), then #, then str.
  2. Decode: start with i = 0. While i is inside the string:
    • Find the first # at or after i; call its index j.
    • Parse s[i..j-1] as the length n.
    • The string is the n characters starting at j + 1. Add it to the result.
    • Move i to j + 1 + n, the start of the next length.

Implementation

Python:

from typing import List


class Codec:
    def encode(self, strs: List[str]) -> str:
        """Encodes a list of strings to a single string."""
        # Each string becomes "<length>#<string>"
        return "".join(f"{len(s)}#{s}" for s in strs)

    def decode(self, s: str) -> List[str]:
        """Decodes a single string to a list of strings."""
        result = []
        i = 0
        while i < len(s):
            # A length has only digits, so the first '#' ends it
            j = s.index("#", i)
            length = int(s[i:j])
            # Copy exactly `length` characters, whatever they are
            result.append(s[j + 1:j + 1 + length])
            i = j + 1 + length
        return result

Java:

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

public class Codec {

    // Encodes a list of strings to a single string.
    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();
        for (String str : strs) {
            // Each string becomes "<length>#<string>"
            sb.append(str.length()).append('#').append(str);
        }
        return sb.toString();
    }

    // Decodes a single string to a list of strings.
    public List<String> decode(String s) {
        List<String> result = new ArrayList<>();
        int i = 0;
        while (i < s.length()) {
            // A length has only digits, so the first '#' ends it
            int j = s.indexOf('#', i);
            int length = Integer.parseInt(s.substring(i, j));
            // Copy exactly `length` characters, whatever they are
            result.add(s.substring(j + 1, j + 1 + length));
            i = j + 1 + length;
        }
        return result;
    }
}

Go:

import (
    "strconv"
    "strings"
)

type Codec struct {
}

// Encodes a list of strings to a single string.
func (codec *Codec) Encode(strs []string) string {
    var sb strings.Builder
    for _, str := range strs {
        // Each string becomes "<length>#<string>"
        sb.WriteString(strconv.Itoa(len(str)))
        sb.WriteByte('#')
        sb.WriteString(str)
    }
    return sb.String()
}

// Decodes a single string to a list of strings.
func (codec *Codec) Decode(s string) []string {
    result := []string{}
    i := 0
    for i < len(s) {
        // A length has only digits, so the first '#' ends it
        j := i + strings.IndexByte(s[i:], '#')
        length, _ := strconv.Atoi(s[i:j])
        // Copy exactly `length` bytes, whatever they are
        result = append(result, s[j+1:j+1+length])
        i = j + 1 + length
    }
    return result
}

JavaScript:

/**
 * Encodes a list of strings to a single string.
 *
 * @param {string[]} strs
 * @return {string}
 */
var encode = function(strs) {
    // Each string becomes "<length>#<string>"
    return strs.map(str => `${str.length}#${str}`).join('');
};

/**
 * Decodes a single string to a list of strings.
 *
 * @param {string} s
 * @return {string[]}
 */
var decode = function(s) {
    const result = [];
    let i = 0;
    while (i < s.length) {
        // A length has only digits, so the first '#' ends it
        const j = s.indexOf('#', i);
        const length = parseInt(s.slice(i, j), 10);
        // Copy exactly `length` characters, whatever they are
        result.push(s.slice(j + 1, j + 1 + length));
        i = j + 1 + length;
    }
    return result;
};

C#:

using System.Collections.Generic;
using System.Text;

public class Codec {

    // Encodes a list of strings to a single string.
    public string encode(IList<string> strs) {
        var sb = new StringBuilder();
        foreach (string str in strs) {
            // Each string becomes "<length>#<string>"
            sb.Append(str.Length).Append('#').Append(str);
        }
        return sb.ToString();
    }

    // Decodes a single string to a list of strings.
    public IList<string> decode(string s) {
        var result = new List<string>();
        int i = 0;
        while (i < s.Length) {
            // A length has only digits, so the first '#' ends it
            int j = s.IndexOf('#', i);
            int length = int.Parse(s.Substring(i, j - i));
            // Copy exactly `length` characters, whatever they are
            result.Add(s.Substring(j + 1, length));
            i = j + 1 + length;
        }
        return result;
    }
}

C++:

#include <string>
#include <vector>
using namespace std;

class Codec {
public:
    // Encodes a list of strings to a single string.
    string encode(vector<string>& strs) {
        string out;
        for (const string& str : strs) {
            // Each string becomes "<length>#<string>"
            out += to_string(str.size());
            out += '#';
            out += str;
        }
        return out;
    }

    // Decodes a single string to a list of strings.
    vector<string> decode(string s) {
        vector<string> result;
        size_t i = 0;
        while (i < s.size()) {
            // A length has only digits, so the first '#' ends it
            size_t j = s.find('#', i);
            size_t length = stoul(s.substr(i, j - i));
            // Copy exactly `length` characters, whatever they are
            result.push_back(s.substr(j + 1, length));
            i = j + 1 + length;
        }
        return result;
    }
};

Complexity Analysis

  • Time: O(N), where N is the total number of characters across all strings. Each string is written once and read once; the # search only scans the few digits of each length.
  • Space: O(N + k) for the encoded string, where k is the number of strings: each one adds only digits + 1 characters (at most 4 here, since lengths are at most 200). Decoding needs O(N) for the result list.

Key Insights

  • A plain separator cannot work on its own. If strings can contain any character, then any separator can appear inside a string, and ["a,b"] and ["a", "b"] would encode to the same text. You need either escaping or framing.
  • Length prefixing never inspects the payload. The decoder jumps over each string by its length, so the string’s content is irrelevant. This is why it is the standard answer and how binary protocols frame messages.
  • The first # after a length is unambiguous. Lengths are digits only, so searching for # from the start of a length can never land inside string data.
  • Escaping must be decoded two characters at a time. The string "/:" encodes to //:/:. A decoder that searches for the first /: would split at index 1 and get it wrong; reading pairs from the left gives // (a /), then :, then /: (end of string).
  • Empty strings need a representation. Both formats emit something for an empty string (/: or 0#), so [""] and ["", ""] decode correctly.

Edge Cases

  1. Empty strings, alone ([""]) or mixed in (["a", "", "b"]): each must produce its own marker.
  2. Strings containing the separator or digits, like "4#x" or "12#": length prefixing copies them blindly; escaping doubles every / and ends each string with /:, so a lone : or # in the data is copied as-is.
  3. Strings that look like an encoding, like "3#abc": they are still just data.
  4. Every character of the 256-character set, including \0 and characters above 127: avoid any format that treats a character as special without escaping it.
  5. A string of 200 characters: the length has three digits, so do not assume a single-digit length.
  6. An empty list (outside the stated constraints): both approaches encode it as "" and decode "" back to an empty list.

Common Mistakes

  1. Joining with a “rare” character such as | or \u0001. The input may contain any ASCII character, so a rare character is still a collision waiting to happen.
  2. Assuming lengths are one digit. Reading only s[i] as the length breaks on strings of 10 or more characters.
  3. Searching for # from the wrong place. Searching from the start of the whole string, or from inside the previous string, finds a # that belongs to the data.
  4. Using split to decode. split on a separator drops or merges empty strings and cannot see escapes.
  5. Storing state in the codec. Encoding and decoding may run on different machines or instances, so decode must work from the string alone.

Interview Tips

  1. Show why the naive join fails first. One collision example, like ["a,b"] versus ["a", "b"], proves you understand the requirement.
  2. Name both fixes, escaping and length prefixing, then pick length prefixing and explain why it never looks at the payload.
  3. Trace an adversarial input, such as ["4#x", "", "#"], through your decoder to show the # inside the data is never treated as structure.
  4. Mention the fixed-width alternative: write every length as, say, 4 characters (or 4 raw bytes). It removes the # but caps the string length.
  5. Connect it to real systems: HTTP chunked encoding, Redis’s RESP protocol and protobuf all frame data with lengths.

Follow-up Questions

  1. How would you encode a list of lists, or a tree of strings? Apply length prefixing recursively, or prefix each list with its element count. Serialize and Deserialize Binary Tree below uses the same framing ideas.
  2. What if the strings are arbitrary Unicode? Decide whether lengths count bytes, UTF-16 units or code points, and use the same unit on both sides; encoding to UTF-8 bytes first is the safest.
  3. How do you make the encoding compact for many short strings? Use a fixed-width binary length, or a variable-length integer (varint) as protobuf does.
  4. What if the encoded data arrives over a stream in chunks? Length prefixing lets the decoder know how many more characters it needs before a string is complete.
  5. How would you detect corrupted input? Add a total count or checksum at the front and validate lengths against the remaining input instead of trusting them.