Encode and Decode Strings

LeetCode 271: Encode and Decode Strings Solution & Explanation

Problem Overview

TL;DR: The optimal solution uses a length-prefixing protocol (Length-Value encoding) to serialize strings, ensuring that special characters inside the strings do not disrupt the decoding process.

The "Encode and Decode Strings" problem asks us to design an algorithm to convert a list of strings into a single string and then reverse the process to retrieve the original list. The challenge lies in the fact that the strings can contain any valid ASCII character, including delimiters or special symbols that might typically be used to separate data. We cannot rely on built-in serialization libraries; we must implement the logic manually. This is a popular interview question for companies like Microsoft because it tests fundamental understanding of data serialization and protocol design.

Brute Force Approach for Encode and Decode Strings

A common naive approach is to join the strings using a specific delimiter character, such as a comma , or a hash #.

Naive Pseudo-code:

function encode(strs):
    return join(strs, "#")

function decode(s):
    return split(s, "#")

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.

Algorithm Strategy: Design Patterns

We will design a stateless protocol for the encode and decode methods.

Encode Strategy

1. Initialize an empty string (or StringBuilder) to hold the result.
2. Iterate through each string in the input list.
3. For each string, calculate its length.
4. Append the string representation of the length, a specific delimiter (e.g., #), and the string content itself to the result.
5. Return the final concatenated string.

Decode Strategy

1. Initialize an empty list to hold the decoded strings.
2. Use a pointer i to traverse the encoded string s.
3. While i is less than the length of s:
   • Find the position of the next delimiter # starting from i.
   • Parse the substring from i to the delimiter as an integer. This is the length of the next string.
   • Move the pointer to the start of the content (immediately after the delimiter).
   • Extract the substring of size length.
   • Add this substring to the list.
   • Move the pointer i past this substring to the start of the next length prefix.
4. Return the list.

This design ensures $O(1)$ ambiguity resolution. The delimiter is only ever searched for before reading the content, never inside the content.

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.

Pattern Reuse Notes

The Design pattern used here—specifically defining a protocol or managing state boundaries—is applicable to several other problems:

• LeetCode 146: LRU Cache: Requires designing a data structure (combining Hash Map and Doubly Linked List) to satisfy specific $O(1)$ constraints.
• LeetCode 155: Min Stack: Involves designing a stack that retrieves the minimum element in $O(1)$ by maintaining parallel state.
• LeetCode 225: Implement Stack using Queues: Requires designing one data structure's behavior using the constraints of another.
• LeetCode 232: Implement Queue using Stacks: Similar to the above, emphasizing internal state management to mimic a different interface.

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.

Reference Implementation

C++ Solution for LeetCode 271

1#include <vector>
2#include <string>
3
4using namespace std;
5
6class Codec {
7public:
8    // Encodes a list of strings to a single string.
9    string encode(vector<string>& strs) {
10        string encodedString = "";
11        for (const string& s : strs) {
12            // Pattern: Length + Delimiter + Content
13            encodedString += to_string(s.length()) + "#" + s;
14        }
15        return encodedString;
16    }
17
18    // Decodes a single string to a list of strings.
19    vector<string> decode(string s) {
20        vector<string> decodedStrings;
21        int i = 0;
22        
23        while (i < s.length()) {
24            // Find the position of the next delimiter
25            size_t delimiterPos = s.find('#', i);
26            
27            // Extract the length of the next string
28            int length = stoi(s.substr(i, delimiterPos - i));
29            
30            // Move pointer to the start of the content
31            i = delimiterPos + 1;
32            
33            // Extract the string content
34            decodedStrings.push_back(s.substr(i, length));
35            
36            // Move pointer past the current string
37            i += length;
38        }
39        
40        return decodedStrings;
41    }
42};

Java Solution for LeetCode 271

1import java.util.ArrayList;
2import java.util.List;
3
4public class Codec {
5
6    // Encodes a list of strings to a single string.
7    public String encode(List<String> strs) {
8        StringBuilder encodedString = new StringBuilder();
9        for (String s : strs) {
10            // Append length, delimiter, then the string itself
11            encodedString.append(s.length()).append("#").append(s);
12        }
13        return encodedString.toString();
14    }
15
16    // Decodes a single string to a list of strings.
17    public List<String> decode(String s) {
18        List<String> decodedStrings = new ArrayList<>();
19        int i = 0;
20        
21        while (i < s.length()) {
22            // Find the delimiter index starting from current position i
23            int delimiterPos = s.indexOf('#', i);
24            
25            // Parse the length from the substring before the delimiter
26            int length = Integer.parseInt(s.substring(i, delimiterPos));
27            
28            // The content starts immediately after the delimiter
29            i = delimiterPos + 1;
30            
31            // Extract the content using the parsed length
32            decodedStrings.add(s.substring(i, i + length));
33            
34            // Advance the pointer past the content
35            i += length;
36        }
37        
38        return decodedStrings;
39    }
40}

Python Solution for LeetCode 271

1class Codec:
2    def encode(self, strs: list[str]) -> str:
3        """Encodes a list of strings to a single string."""
4        encoded_string = ""
5        for s in strs:
6            # Pattern: Length + Delimiter + Content
7            encoded_string += str(len(s)) + "#" + s
8        return encoded_string
9
10    def decode(self, s: str) -> list[str]:
11        """Decodes a single string to a list of strings."""
12        decoded_strings = []
13        i = 0
14        
15        while i < len(s):
16            # Find the delimiter starting from index i
17            j = s.find("#", i)
18            
19            # The length is the number before the delimiter
20            length = int(s[i:j])
21            
22            # Move pointer to the start of the content
23            i = j + 1
24            
25            # Extract the string content
26            decoded_strings.append(s[i : i + length])
27            
28            # Move pointer past the current string
29            i += length
30            
31        return decoded_strings