Encode and Decode Strings

How it works

Instead of storing all string lengths first and then appending the strings, we can directly attach each string to its length.
For every string, we write length#string.
The # character acts as a clear boundary between the length and the actual content, and using the length ensures we know exactly how many characters to read—no matter what characters appear in the string itself.
During decoding, we simply read characters until we reach # to find the length, then extract exactly that many characters as the string.
This approach is both simpler and more efficient because it avoids building separate sections for lengths and content.

Steps

Encoding

1. Initialize an empty result builder (or list of string parts).
2. For each string in the list:
   • Compute its length.
   • Append "length#string" to the builder.
3. Return the final encoded string.

Decoding

1. Initialize an empty list for the decoded strings and a pointer i = 0.
2. While i is within the bounds of the encoded string:
   • Move a pointer j forward until it finds '#' — this segment represents the length.
   • Convert the substring s[i:j] into an integer length.
   • Move i to the character right after '#'.
   • Extract the next length characters — this is the original string.
   • Append the extracted string to the result list.
   • Move i forward by length to continue decoding the next segment.
3. Return the list of decoded strings.

Complexity

• Time complexity: O(m + n) for each encode() and decode() function calls.
• Space complexity: O(m + n) for each encode() and decode() function calls.

Where m is the sum of lengths of all the strings and n is the number of strings.

Things to watch for

Using a Delimiter That Can Appear in the Strings

Choosing a simple delimiter like a comma or space will break decoding if that character appears inside the original strings. The length-prefixing approach avoids this by using the length to know exactly how many characters to read, making the content irrelevant.

Not Handling Empty Strings or Empty Lists

Edge cases like an empty input list or strings that are themselves empty ("") require careful handling. Ensure your encoding distinguishes between an empty list and a list containing one empty string, and that decoding correctly reconstructs zero-length strings.

Parsing Length Incorrectly for Multi-Digit Numbers

When the length of a string is 10 or more, the length prefix becomes multi-digit. Ensure you read all digits before the # separator rather than just assuming a single digit. Using a loop to collect characters until reaching # handles this correctly.

from typing import List

class Solution:

    def encode(self, strs: List[str]) -> str:
        res = []
        for s in strs:
            res.append(str(len(s)))
            res.append("#")
            res.append(s)
        return "".join(res)

    def decode(self, s: str) -> List[str]:
        res = []
        i = 0

        while i < len(s):
            j = i
            while s[j] != '#':
                j += 1
            length = int(s[i:j])
            i = j + 1
            j = i + length
            res.append(s[i:j])
            i = j

        return res

class Solution {
public:
    string encode(vector<string>& strs) {
        string res;
        for (const string& s : strs) {
            res.append(to_string(s.size()));
            res.push_back('#');
            res.append(s);
        }
        return res;
    }

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