1. Understand the Problem

• You are given a list of strings and need to encode it into a single string so that it can be easily decoded back to the original list.

• Key idea:

  • You must design both functions — encode and decode.

  • Encoding must be unambiguous (no confusion about where one word ends).

  • The encoding format must handle any characters, including #, spaces, or even empty strings.

2. Ask Clarifying Questions

• Can the list contain empty strings?

• Are there any special characters like # or digits in the strings?

• What is the expected input size (number of strings and total length)?

• Should the output be space-efficient or time-efficient?

• What time and space complexity are acceptable?

3. Work Through Examples

Try random examples to clarify the pattern:

1. Example 1:

Input: ["leet", "code"]
Encode → "4#leet4#code"
Decode → ["leet", "code"]

1. Example 2 (edge case with empty string):

Input: ["", "abc"]
Encode → "0#3#abc"
Decode → ["", "abc"]

1. Example 3 (special characters):

Input: ["#love#", "python"]
Encode → "6##love#6#python"
Decode → ["#love#", "python"]

The interviewer may correct or guide if your format could break.

4. Brainstorm 2–3 Solutions

4.1. Naive Solution:

• Join strings with a delimiter like # or ,.

• ❌ Problem: Fails if the string itself contains the delimiter.

Example: “2,3,#hifoo”

4.2. Optimized Solution (Prefix-Length Encoding):

• Encode each string as #.

• Decode by reading the length first, then extracting that many characters.

• ✅ Works with all characters, including # or spaces.

Example: “2#hi3#foo”

4.3. Complexity:

• Time: O(N) for both encode and decode.

• Space: O(N) for storing the output.

5. Implement Solution

5.1. Naive Solution

• Decode to: “2,3,#hifoo”

class Solution:
    def encode(self, strs: List[str]) -> str:
        if not strs:
            return ""
        sizes, res = [], ""
        for s in strs:
            sizes.append(len(s))
        for sz in sizes:
            res += str(sz)
            res += ','
        res += '#'
        for s in strs:
            res += s
        return res

    def decode(self, s: str) -> List[str]:
        if not s:
            return []
        sizes, res, i = [], [], 0
        while s[i] != '#':
            cur = ""
            while s[i] != ',':
                cur += s[i]
                i += 1
            sizes.append(int(cur))
            i += 1
        i += 1
        for sz in sizes:
            res.append(s[i:i + sz])
            i += sz
        return res

• Time complexity: O(m).

• Space complexity: O(m + n).

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

5.2. Optimize Solution

• Decode to: “2#hi3#foo”

class Codec:
    def encode(self, strs):
        res = ""
        for s in strs:
            res += str(len(s)) + "#" + s
        return res

    def decode(self, s):
        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

• Time complexity: O(m).

• Space complexity: O(m + n) => But do not need another array.

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

6. Test Your Code

Dry run using examples from step 3:

• ✅ [“leet”, “code”] → “4#leet4#code” → [“leet”, “code”]

• ✅ [””, “abc”] → “0#4#abc” → [””, “abc”]

• ✅ [“#love#”, “python”] → “6##love#6#python” → [“#love#”, “python”]