NUHMAN.com

Introduction

LeetCode 271: Encode and Decode Strings is a popular design question, often seen in interviews at big tech companies.

The problem is about implementing a way to encode a list of strings into a single string, and then decode it back into the original list — with all string data preserved accurately, including special characters like colons, slashes, etc.

This is essentially a custom implementation of string serialization/deserialization.

Problem Statement

Design an algorithm to encode a list of strings into a single string.

The encoded string is then sent over the network and is decoded back to the original list of strings.

Implement the Codec class with two methods:

• encode(strs: List[str]) -> str
• decode(s: str) -> List[str]

Example

python

Input: ["lint","code","love","you"]
Encoded: "4#lint4#code4#love3#you"
Decoded: ["lint","code","love","you"]

✅ Step-by-Step Solution in Python

We’ll use length prefixing:

Each string will be encoded as:

<length>#<string>

This way, even if the string contains # or other special characters, we can still decode it unambiguously.

🔁 Step 1: Encoding Logic

For each string in the list:

• Calculate its length
• Concatenate length + '#' + string

🔁 Step 2: Decoding Logic

• Read the length until you hit #
• Use that length to extract the actual string
• Repeat until the end

✅ Python Code

python

class Codec:
    def encode(self, strs: list[str]) -> str:
        res = ""
        for s in strs:
            res += f"{len(s)}#{s}"
        return 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])
            res.append(s[j+1 : j+1+length])
            i = j + 1 + length
        return res

🧪 Dry Run

Input: ["hi", "there"]

Encode:

• "hi" → "2#hi"
• "there" → "5#there"

Encoded: "2#hi5#there"

Decode:

• Read 2 → "hi"
• Read 5 → "there"
• ✅ Output: ["hi", "there"]

⏱️ Time and Space Complexity

OperationTime ComplexitySpace ComplexityEncodeO(n)O(n)DecodeO(n)O(n)

Where n is the total number of characters across all strings.

⚠️ Edge Cases

• Empty list [] → encode to "" → decode returns []
• Strings with special characters (like #, digits, etc.) → handled safely via length-prefixing
• Strings containing empty strings: ["", "a", ""] → works perfectly

🧠 Why Length + # Works

• Unlike using a delimiter alone (e.g., comma), which is ambiguous if strings contain commas, prefixing with length ensures unambiguous decoding.

✅ Conclusion

LeetCode 271: Encode and Decode Strings is an excellent design problem that teaches:

• Custom serialization techniques
• Robustness in string parsing
• Dealing with edge cases and input validation