Encode and Decode Strings

Problem Description

Design an algorithm to encode a list of strings to a single string. The encoded string is then sent over the network and is decoded back to the original list of strings.

Examples

Constraints

• 1 ≤ dummy_input.length ≤ 200
• 0 ≤ dummy_input[i].length ≤ 200
• dummy_input[i] contains any possible ASCII characters.

The Need for a Delimiter That Cannot Be Mimicked

The simple idea is joining strings with a special character like a comma or hash. This immediately breaks if the input strings themselves contain that character. If the input is ["hello,world", "test"], joining with a comma yields hello,world,test, which decodes incorrectly to three strings.

To resolve this, you must prefix each string with its length followed by a non-numeric delimiter. For example, "hello" becomes "5#hello". During decoding, you read the integer prefix, skip the delimiter, and slice exactly that many characters. The content of the string is never confused with the delimiter because the prefix dictates exactly how many characters to consume.

Solution 1: Length-Prefix Encoding

Prefix each string with its length and a delimiter character.

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 s : strs) {
            // append length, delimiter, and string
            sb.append(s.length()).append('#').append(s);
        }
        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()) {
            int delimiterIdx = s.indexOf('#', i);
            int length = Integer.parseInt(s.substring(i, delimiterIdx));
            i = delimiterIdx + 1;
            result.add(s.substring(i, i + length));
            i += length;
        }
        return result;
    }
}

class Codec:
    def encode(self, strs: list[str]) -> str:
        # join each string prefixed by its length and a delimiter
        return "".join(f"{len(s)}#{s}" for s in strs)

    def decode(self, s: str) -> list[str]:
        result = []
        i = 0
        while i < len(s):
            # find the delimiter position starting from current index
            j = s.find('#', i)
            length = int(s[i:j])
            i = j + 1
            result.append(s[i : i + length])
            i += length
        return result

#include <string>
#include <vector>

class Codec {
public:
    // Encodes a list of strings to a single string.
    std::string encode(std::vector<std::string>& strs) {
        std::string encoded = "";
        for (const std::string& s : strs) {
            encoded += std::to_string(s.length()) + "#" + s;
        }
        return encoded;
    }

    // Decodes a single string to a list of strings.
    std::vector<std::string> decode(std::string s) {
        std::vector<std::string> result;
        int i = 0;
        while (i < s.length()) {
            int j = s.find('#', i);
            int length = std::stoi(s.substr(i, j - i));
            i = j + 1;
            result.push_back(s.substr(i, length));
            i += length;
        }
        return result;
    }
};

Complexity Analysis:

• Time Complexity: O(n) where n is the total number of characters across all strings. Each character is processed once during encoding and once during decoding.
• Space Complexity: O(1) auxiliary space, as we only allocate memory for the output structures.

Where it breaks: If the input list contains extremely long strings that cause the length prefix representation to exceed standard integer bounds during parsing, this could crash. In practice, the string length constraint of 200 prevents this.

Why Not Use Non-Printable ASCII Characters?

Some solutions use a special non-printable character like ASCII 257 as a delimiter. While this works on simple test platforms, it is brittle. If the system transmitting the data filters or translates non-printable characters, the delimiter will be corrupted. The length-prefix approach relies entirely on standard printable characters.

Common Mistakes

• Using a plain delimiter without length prefix. If you choose a separator like # without including the length, any # inside the original string will break your decoding logic.
• Parsing the length incorrectly when it has multiple digits. If the string length is 10, the prefix is 10#. Your parser must search for the first occurrence of the delimiter to determine where the number ends.
• Off-by-one errors on index manipulation. Be careful to advance your index pointer past both the delimiter and the consumed string slice.

Frequently Asked Questions

Can the delimiter character appear in the input strings? Yes. Since the decoder reads the exact length first, it knows exactly how many characters to skip. Any delimiter characters within the string are skipped automatically.

How does this handle empty strings in the input list? An empty string is encoded as 0#. The decoder reads the length as 0, appends an empty string, and continues processing from the next character.

What does this problem test in interviews? It tests your ability to design robust data serialization formats, manage pointers carefully, and handle edge cases like empty strings, single character strings, and strings containing delimiters.

← All Problems