Encode and Decode Strings

Description

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

You need to implement two functions:

encode(strs): Takes a list of strings and converts it into a single encoded string.
decode(s): Takes the encoded string and converts it back into the original list of strings.

The strings may contain any of the 256 valid ASCII characters, including special characters, digits, delimiters, and even empty strings. Your encoding must handle all of these correctly so that the decode function perfectly reconstructs the original list without any loss of information.

You may not use any built-in serialization methods — the purpose of this problem is to design the encoding and decoding algorithms yourself.

Examples

Example 1

Input: strs = ["lint", "code", "love", "you"]

Output: ["lint", "code", "love", "you"]

Explanation: The encode function converts the list into a single string using some encoding scheme. The decode function then reconstructs the original list perfectly. For example, one valid encoding could be: "4#lint4#code4#love3#you" — where each string is prefixed with its length followed by a '#' separator.

Example 2

Input: strs = ["we", "say", ":", "yes"]

Output: ["we", "say", ":", "yes"]

Explanation: Notice that one of the strings is just the colon character ":". If we naively used ":" as a delimiter to join strings, we would not be able to tell whether a colon in the encoded string is a delimiter or part of the original data. A robust encoding scheme handles this correctly.

Example 3

Input: strs = ["", "", ""]

Output: ["", "", ""]

Explanation: The list contains three empty strings. A correct encoding must preserve both the count of strings and the fact that each one is empty. A length-based encoding like "0#0#0#" makes this unambiguous.

Constraints

0 ≤ strs.length ≤ 200
0 ≤ strs[i].length ≤ 200
strs[i] contains any possible characters out of 256 valid ASCII characters

Editorial

Brute Force

Intuition

The most natural first attempt is to pick a special character as a delimiter and join all strings with it. For example, we might join the strings using a comma: ["hello", "world"] becomes "hello,world". To decode, we split by commas.

Think of it like writing sentences on a postcard. You put a dash between each sentence so the reader knows where one ends and the next begins.

The problem arises when the strings themselves contain the delimiter character. If one of the strings is "a,b", and our delimiter is a comma, then encoding ["a,b", "c"] as "a,b,c" becomes ambiguous — we cannot tell if it was originally ["a,b", "c"] or ["a", "b", "c"] or ["a", "b,c"].

To handle this, we introduce an escape mechanism. Before joining, we escape any occurrence of the delimiter inside the strings by prefixing it with a special escape character (like backslash). We also escape the escape character itself to avoid further ambiguity. During decoding, we scan character by character: an unescaped delimiter means "split here", while an escaped delimiter is part of the original string.

Step-by-Step Explanation

Let's trace through with strs = ["we", "say", ":", "yes"], using '#' as delimiter and '/' as escape character:

Encoding:

Step 1: Process string "we". No '#' or '/' characters found. Output so far: "we"

Step 2: Add delimiter '#'. Output: "we#"

Step 3: Process string "say". No special characters. Output: "we#say"

Step 4: Add delimiter '#'. Output: "we#say#"

Step 5: Process string ":". The colon is not our delimiter or escape char, so no escaping needed. Output: "we#say#:"

Step 6: Add delimiter '#'. Output: "we#say#:#"

Step 7: Process string "yes". No special characters. Output: "we#say#:#yes"

Encoded result: "we#say#:#yes"

Decoding:

Step 8: Scan character by character. Read 'w', 'e' → current string = "we"

Step 9: Hit unescaped '#'. Split! First string: "we". Start new string.

Step 10: Read 's', 'a', 'y' → current string = "say"

Step 11: Hit unescaped '#'. Split! Second string: "say". Start new string.

Step 12: Read ':' → current string = ":"

Step 13: Hit unescaped '#'. Split! Third string: ":". Start new string.

Step 14: Read 'y', 'e', 's' → current string = "yes"

Step 15: End of encoded string. Fourth string: "yes".

Result: ["we", "say", ":", "yes"]

Escape-Based Encoding — Character-by-Character Scan — Watch how we scan each character of the encoded string, splitting at unescaped delimiters and reconstructing the original strings one by one.

Algorithm

Encode:

Choose a delimiter character (e.g., '#') and an escape character (e.g., '/')
For each string in the list:
a. Replace every '/' with '//' (escape the escape character)
b. Replace every '#' with '/#' (escape the delimiter)
Join the escaped strings with '#' between them

Decode:

Scan the encoded string character by character
If you see the escape character '/':
a. Look at the next character — it is either '/' or '#'
b. Append the next character to the current string (un-escape it)
c. Skip ahead by 2
If you see an unescaped '#': finalize the current string, add to result, start a new string
Otherwise: append the character to the current string
After the loop, add the last accumulated string to the result

Code

class Codec {
public:
    string encode(vector<string>& strs) {
        string encoded = "";
        for (int k = 0; k < strs.size(); k++) {
            for (char c : strs[k]) {
                if (c == '/' || c == '#') {
                    encoded += '/';
                }
                encoded += c;
            }
            if (k != strs.size() - 1) {
                encoded += '#';
            }
        }
        return encoded;
    }

    vector<string> decode(string s) {
        vector<string> result;
        string current = "";
        int i = 0;
        while (i < s.size()) {
            if (s[i] == '/') {
                current += s[i + 1];
                i += 2;
            } else if (s[i] == '#') {
                result.push_back(current);
                current = "";
                i++;
            } else {
                current += s[i];
                i++;
            }
        }
        result.push_back(current);
        return result;
    }
};

class Codec:
    def encode(self, strs: list[str]) -> str:
        encoded = ""
        for k, s in enumerate(strs):
            for c in s:
                if c == '/' or c == '#':
                    encoded += '/'
                encoded += c
            if k != len(strs) - 1:
                encoded += '#'
        return encoded

    def decode(self, s: str) -> list[str]:
        result = []
        current = ""
        i = 0
        while i < len(s):
            if s[i] == '/':
                current += s[i + 1]
                i += 2
            elif s[i] == '#':
                result.append(current)
                current = ""
                i += 1
            else:
                current += s[i]
                i += 1
        result.append(current)
        return result

public class Codec {
    public String encode(List<String> strs) {
        StringBuilder encoded = new StringBuilder();
        for (int k = 0; k < strs.size(); k++) {
            for (char c : strs.get(k).toCharArray()) {
                if (c == '/' || c == '#') {
                    encoded.append('/');
                }
                encoded.append(c);
            }
            if (k != strs.size() - 1) {
                encoded.append('#');
            }
        }
        return encoded.toString();
    }

    public List<String> decode(String s) {
        List<String> result = new ArrayList<>();
        StringBuilder current = new StringBuilder();
        int i = 0;
        while (i < s.length()) {
            if (s.charAt(i) == '/') {
                current.append(s.charAt(i + 1));
                i += 2;
            } else if (s.charAt(i) == '#') {
                result.add(current.toString());
                current = new StringBuilder();
                i++;
            } else {
                current.append(s.charAt(i));
                i++;
            }
        }
        result.add(current.toString());
        return result;
    }
}

Complexity Analysis

Time Complexity: O(N) where N is the total number of characters across all strings

Both encoding and decoding scan each character exactly once. The escaping step in encoding may double some characters (those that match the delimiter or escape character), but the total work is still proportional to the input size.

Space Complexity: O(N)

The encoded string stores all original characters plus some escape characters. In the worst case (every character is a delimiter or escape character), the encoded string can be up to 2N characters long, which is still O(N).

Why This Approach Is Not Efficient

The escape-based approach works correctly but has a practical drawback: in the worst case, when every character in the input happens to be the delimiter or escape character, the encoded string can nearly double in size. Every '#' becomes '/#' and every '/' becomes '//', which means the encoded output can be up to twice the length of the original input.

Additionally, the decoding logic is more complex than necessary. We must carefully track escaped vs. unescaped characters, which introduces potential for bugs — especially if the delimiter or escape character changes.

A simpler and more robust approach exists: length-prefixed encoding. Instead of worrying about what characters appear inside the strings, we simply record each string's length before the string itself. The decoder reads the length, then extracts exactly that many characters — no escaping needed, no ambiguity possible, regardless of what characters the strings contain. This also avoids any inflation of the encoded string size.

Optimal Approach - Length Prefix Encoding

Intuition

Instead of trying to find a safe delimiter and escaping conflicts, we take a completely different approach: for each string, we first write its length as a number, then a separator character (like '#'), and then the string content itself.

Imagine you are packing items into a box for shipping. Instead of putting dividers between items (which could be confused with the items themselves), you attach a label to each item saying "this item is 5 inches long", "this item is 3 inches long", etc. The person unpacking reads each label, measures out exactly that many inches, and knows precisely where each item starts and ends — regardless of what the item looks like.

For example, encoding ["lint", "code"] produces: "4#lint4#code". To decode:

Read digits until you hit '#': you get length = 4
Read the next 4 characters: "lint"
Read digits until '#': length = 4
Read the next 4 characters: "code"

This approach is elegant because:

The '#' after the length is never ambiguous — we know to stop reading digits at '#' and then take exactly length characters, so any '#' that appears inside a string is harmlessly consumed as part of the content.
Empty strings encode as "0#" — length 0, read 0 characters.
Strings containing digits, '#', or any ASCII character all work without modification.

Step-by-Step Explanation

Let's trace with strs = ["we", "say", ":", "yes"]:

Encoding:

Step 1: Process "we". Length = 2. Append "2#we". Encoded so far: "2#we"

Step 2: Process "say". Length = 3. Append "3#say". Encoded so far: "2#we3#say"

Step 3: Process ":". Length = 1. Append "1#:". Encoded so far: "2#we3#say1#:"

Step 4: Process "yes". Length = 3. Append "3#yes". Encoded: "2#we3#say1#:3#yes"

Decoding "2#we3#say1#:3#yes":

Step 5: Start at i=0. Read digits until '#': read '2', hit '#' at i=1. Length = 2. Skip '#'. Extract s[2..3] = "we". Move i to 4.

Step 6: At i=4. Read '3', hit '#' at i=5. Length = 3. Extract s[6..8] = "say". Move i to 9.

Step 7: At i=9. Read '1', hit '#' at i=10. Length = 1. Extract s[11..11] = ":". Move i to 12.

Step 8: At i=12. Read '3', hit '#' at i=13. Length = 3. Extract s[14..16] = "yes". Move i to 17.

Step 9: i=17 >= length of encoded string. Done.

Result: ["we", "say", ":", "yes"]

Length-Prefix Decoding — Reading Lengths Then Extracting Content — Watch how the decoder reads the length number, skips the '#' separator, and then extracts exactly that many characters — no ambiguity regardless of string content.

Algorithm

Encode:

For each string in the list:
a. Write the string's length as a decimal number
b. Write a '#' separator
c. Write the string itself
Concatenate everything into one encoded string

Decode:

Initialize pointer i = 0 and empty result list
While i < length of encoded string:
a. Read digits starting at i until you encounter '#' — this gives you the length
b. Skip the '#' character
c. Extract the next length characters as a string
d. Add the extracted string to the result
e. Advance i past the extracted string
Return the result list

Code

class Codec {
public:
    string encode(vector<string>& strs) {
        string encoded = "";
        for (const string& s : strs) {
            encoded += to_string(s.size()) + "#" + s;
        }
        return encoded;
    }

    vector<string> decode(string s) {
        vector<string> result;
        int i = 0;
        while (i < s.size()) {
            int j = i;
            while (s[j] != '#') {
                j++;
            }
            int length = stoi(s.substr(i, j - i));
            string str = s.substr(j + 1, length);
            result.push_back(str);
            i = j + 1 + length;
        }
        return result;
    }
};

class Codec:
    def encode(self, strs: list[str]) -> str:
        encoded = ""
        for s in strs:
            encoded += str(len(s)) + "#" + s
        return encoded

    def decode(self, s: str) -> list[str]:
        result = []
        i = 0
        while i < len(s):
            j = i
            while s[j] != '#':
                j += 1
            length = int(s[i:j])
            result.append(s[j + 1 : j + 1 + length])
            i = j + 1 + length
        return result

public class Codec {
    public String encode(List<String> strs) {
        StringBuilder encoded = new StringBuilder();
        for (String s : strs) {
            encoded.append(s.length()).append('#').append(s);
        }
        return encoded.toString();
    }

    public List<String> decode(String s) {
        List<String> result = new ArrayList<>();
        int i = 0;
        while (i < s.length()) {
            int j = i;
            while (s.charAt(j) != '#') {
                j++;
            }
            int length = Integer.parseInt(s.substring(i, j));
            result.add(s.substring(j + 1, j + 1 + length));
            i = j + 1 + length;
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(N) where N is the total number of characters across all strings

Encoding iterates through every character once to build the encoded string. The length computation for each string is O(1). Decoding also processes each character exactly once — reading the length digits and extracting the substring are linear operations in total.

Space Complexity: O(N)

The encoded string stores all original characters plus a small overhead for the length prefixes. Each length prefix is at most a few digits (since strings are at most 200 characters), so the overhead is negligible. The total encoded size is O(N + k) where k is the number of strings, which simplifies to O(N).

Compared to the escape-based approach, this method never inflates the string beyond a small constant overhead per string. Even if every character in the input is '#' or any special character, the encoded string is only slightly larger than the original — never doubled.