Problem Overview

In this problem, we need to design two functions:

encode(strs)
decode(s)

The encode function takes a list of strings and converts it into a single string. The decode function takes that encoded string and converts it back into the original list.

The important challenge is that each string can contain any ASCII character, including special characters like #, spaces, numbers, or even empty strings.

So we need an encoding format that is reliable and easy to decode.

Key Idea

A simple delimiter-based approach, like joining strings with #, will not work because the strings themselves may contain #.

Instead, we store each string in this format:

length#string

For example:

["Hello", "World"]

becomes:

5#Hello5#World

Here, 5 tells us the length of "Hello", and # separates the length from the actual string.

Encoding

For each string, we append:

str(len(string)) + "#" + string

So if the string is "Hello", we store:

5#Hello

This makes it clear where each string starts and ends.

Decoding

To decode, we scan the encoded string from left to right.

First, we find the # symbol. Everything before it is the length of the next string.

Then, using that length, we extract exactly that many characters after the #.

After extracting the string, we move the pointer forward and repeat the process.

Code

from typing import List


class Solution:

    def encode(self, strs: List[str]) -> str:
        res = ""

        for string in strs:
            res += str(len(string)) + "#" + string

        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])

            i = j + 1
            j = i + length

            res.append(s[i:j])

            i = j

        return res

Example Walkthrough

Input:

["Hello", "World"]

Encoded string:

5#Hello5#World

Decoding steps:

First, we read 5, so the next string has length 5.

We extract:

Hello

Then we read the next 5, so the next string also has length 5.

We extract:

World

Final output:

["Hello", "World"]

Why This Works

This solution works because the length tells us exactly how many characters to read.

Even if the string contains #, numbers, spaces, or special characters, it does not matter. We are not relying on a delimiter inside the string itself. We only use # to separate the length from the string.

For example:

["abc#def"]

would be encoded as:

7#abc#def

The decoder reads length 7, then extracts exactly 7 characters.

Time Complexity

Encoding takes:

O(n)

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

Decoding also takes:

O(n)

because we scan through the encoded string once.

Space Complexity

The space complexity is:

O(n)

because we store the encoded string and the decoded result.

Final Thoughts

The main trick in this problem is avoiding unreliable delimiters. Since the strings can contain any ASCII character, using only a separator is not safe.

By storing the length of each string before the string itself, we create a format that is easy to encode, easy to decode, and handles all edge cases, including empty strings and strings with special characters.