Time Complexity: $O(N)$, where $N$ is the total number of characters. Why it fails: This approach fails correctness tests immediately. If the input strings themselves contain the chosen delimiter (e.g., the input is ["hello", "wor#ld"]), the split operation during decoding will interpret the # inside "wor#ld" as a separator, resulting in an incorrect list: ["hello", "wor", "ld"].

Attempts to fix this by "escaping" the delimiter (e.g., replacing # with ##) add significant complexity to the implementation and increase the processing time and space overhead, making them suboptimal for an interview setting.

Core Insight for Encode and Decode Strings

The fundamental difficulty in LeetCode 271 is distinguishing between "control characters" (delimiters) and "data characters" (content). Since the content can contain any character, no single character can serve as a safe global delimiter.

The solution is to separate metadata (the length of the string) from the data itself. By storing the length of the string before the string content, we know exactly how many characters to read during decoding.

This approach is known as Length-Prefixing or TLV (Type-Length-Value) encoding (though here we only need Length and Value).

Invariant: For every string s in the list, we append length(s) followed by a separator (like #) and then the string s itself. Structure: [Length] + [Separator] + [String Content]

Even if the string content contains the separator #, the decoding logic will not be confused because it relies on the numerical Length prefix to determine exactly where the current string ends. The separator exists solely to distinguish the Length digits from the start of the String Content.

Visual Description: Imagine the encoded string as a stream of bytes. The decoder acts as a parser. It reads numeric characters until it hits a delimiter. This number tells the parser, "The next $L$ characters belong to the current string." The parser then jumps over those $L$ characters, treats them strictly as data (ignoring any symbols inside), and then expects the next segment to begin with a new length number.

Execution Flow

Consider the input: ["Leet", "Code#1"]

Encoding Process:

1. First String ("Leet"):
   • Length: 4
   • Format: 4 + # + Leet
   • Result: "4#Leet"
2. Second String ("Code#1"):
   • Length: 6
   • Format: 6 + # + Code#1
   • Result: "4#Leet6#Code#1"

Decoding Process:

1. State: i = 0, Encoded String: "4#Leet6#Code#1"
2. Step 1:
   • Find delimiter # starting from i=0. Found at index 1.
   • Parse length: Substring 0 to 1 is "4". Length = 4.
   • Content Start: Index 2 (1 + 1).
   • Extract: Read 4 chars from index 2 -> "Leet".
   • Update i: 2 + 4 = 6.
   • List: ["Leet"]
3. Step 2:
   • Find delimiter # starting from i=6. Found at index 7.
   • Parse length: Substring 6 to 7 is "6". Length = 6.
   • Content Start: Index 8 (7 + 1).
   • Extract: Read 6 chars from index 8 -> "Code#1". (Note: The internal # is treated as data).
   • Update i: 8 + 6 = 14.
   • List: ["Leet", "Code#1"]
4. End: i equals string length. Return list.

Proof of Correctness

The correctness relies on the invariant that the integer prefix accurately reflects the byte count of the subsequent data.

1. Uniqueness: The combination of length + delimiter creates a unique header for every packet of data.
2. Boundary Integrity: Since we read exactly length characters, we are guaranteed to stop exactly at the end of the current string. The next character processed will necessarily be the start of the next length prefix (or the end of the input).
3. Data Transparency: Because the parser jumps over the content based on count rather than scanning for a terminator, the content can include any character sequence without confusing the parser.

Reference Implementation

C++ Solution for LeetCode 271

cpp
#include <vector>
#include <string>

using namespace std;

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

    // Decodes a single string to a list of strings.
    vector<string> decode(string s) {
        vector<string> decodedStrings;
        int i = 0;
        
        while (i < s.length()) {
            // Find the position of the next delimiter
            size_t delimiterPos = s.find('#', i);
            
            // Extract the length of the next string
            int length = stoi(s.substr(i, delimiterPos - i));
            
            // Move pointer to the start of the content
            i = delimiterPos + 1;
            
            // Extract the string content
            decodedStrings.push_back(s.substr(i, length));
            
            // Move pointer past the current string
            i += length;
        }
        
        return decodedStrings;
    }
};

Java Solution for LeetCode 271

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 encodedString = new StringBuilder();
        for (String s : strs) {
            // Append length, delimiter, then the string itself
            encodedString.append(s.length()).append("#").append(s);
        }
        return encodedString.toString();
    }

    // Decodes a single string to a list of strings.
    public List<String> decode(String s) {
        List<String> decodedStrings = new ArrayList<>();
        int i = 0;
        
        while (i < s.length()) {
            // Find the delimiter index starting from current position i
            int delimiterPos = s.indexOf('#', i);
            
            // Parse the length from the substring before the delimiter
            int length = Integer.parseInt(s.substring(i, delimiterPos));
            
            // The content starts immediately after the delimiter
            i = delimiterPos + 1;
            
            // Extract the content using the parsed length
            decodedStrings.add(s.substring(i, i + length));
            
            // Advance the pointer past the content
            i += length;
        }
        
        return decodedStrings;
    }
}

Python Solution for LeetCode 271

python
class Codec:
    def encode(self, strs: list[str]) -> str:
        """Encodes a list of strings to a single string."""
        encoded_string = ""
        for s in strs:
            # Pattern: Length + Delimiter + Content
            encoded_string += str(len(s)) + "#" + s
        return encoded_string

    def decode(self, s: str) -> list[str]:
        """Decodes a single string to a list of strings."""
        decoded_strings = []
        i = 0
        
        while i < len(s):
            # Find the delimiter starting from index i
            j = s.find("#", i)
            
            # The length is the number before the delimiter
            length = int(s[i:j])
            
            # Move pointer to the start of the content
            i = j + 1
            
            # Extract the string content
            decoded_strings.append(s[i : i + length])
            
            # Move pointer past the current string
            i += length
            
        return decoded_strings

These problems all share the theme of Design, where the focus is on structure, constraints, and API correctness rather than pure algorithmic search or optimization.

"Can I use JSON or Base64?"

While technically feasible, interviewers specifically forbid "built-in serialization methods." Using json.dumps or similar libraries defeats the purpose of the "Design" pattern exercise, which is to implement the low-level protocol logic yourself.

"What if the string is empty?"

A common mistake is forgetting to handle empty strings. The length-prefix approach handles this naturally: an empty string is encoded as 0#. The decoder reads length 0, extracts an empty substring, and moves on correctly.

"Why do we need the delimiter # between the length and the string?"

Without the delimiter, we cannot distinguish where the length number ends and the string begins if the string starts with a digit. For example, if we encode length 12 and string "34" as "1234", the decoder doesn't know if the length is 1, 12, or 123. The delimiter makes the boundary of the length integer explicit.