LeetCode 271 - Encode and Decode Strings

This Medium problem asks us to encode a list of strings into one string and then reconstruct the original list exactly. A delimiter by itself is ambiguous when the same character can appear in the content, so this solution records each string’s length before its body.

Problem link and explanation

Problem link: 271. Encode and Decode Strings
Summary: Implement an encode function that converts a list of strings into one string and a decode function that restores the original list.

Consider this input:

["leet", "co%de", "", "soul"]

Joining the values with % does not distinguish the delimiter between strings from the % already inside co%de. Empty strings introduce another ambiguous case because consecutive delimiters would need an additional interpretation rule.

This solution stores each value as length + delimiter + body.

4%leet5%co%de0%4%soul

Approach

The encoder writes the length of each string, adds % to mark the end of that length, and then appends the string body.

answer += f"{len(s)}%{s}"

The % does not mark the end of the body. It only marks where the numeric length ends. Even if % appears inside the body, the decoder can read exactly the number of characters specified by the prefix.

The decoder starts left and right at the beginning of the next length field. It moves right until it reaches %, then converts the characters between left and right into an integer.

while s[right] != "%":
    right += 1

num_len = int(s[left:right])

The body starts immediately after the delimiter. Slicing num_len characters from that position restores one string.

start = right + 1
word = s[start : start + num_len]

After restoring the string, both pointers move to the first character of the next length field.

left = start + num_len
right = left

Troubleshooting

As mentioned above, using a delimiter and calling split breaks when the input contains the same character. The problem allows arbitrary characters in each string, so no chosen delimiter is guaranteed to be absent from the body.

I initially considered doubling the delimiter or adding an escape rule. Either option requires the encoder and decoder to maintain more exception-handling rules. Recording the length avoids parsing the body altogether: the decoder advances by an exact number of characters. An empty string is recorded with length zero, and a % inside the body is consumed as ordinary content.

The same boundary problem appears in network protocols and file formats, where terminators, explicit lengths, and chunks identify where one piece of data ends. I plan to cover separately how those techniques were developed and why different systems adopted them.

Complexity analysis

Let L be the total length of the encoded string.

Time complexity
- decode reads each length field and body once, so it takes O(L) time.
- The current encode implementation repeatedly concatenates immutable strings. In the worst case, copying the accumulated result each time can increase the cost to O(L²). Collecting the pieces in a list and joining them reduces the encoding cost to O(L).
Space complexity: O(L)
- encode creates the encoded string, and decode stores the reconstructed list of strings.

Implementation code

class Solution:
    def encode(self, strs: list[str]) -> str:
        answer = ""
        for s in strs:
            answer += f"{len(s)}%{s}"
        return answer

    def decode(self, s: str) -> list[str]:
        left = 0
        right = 0
        str_len = len(s)

        result = []
        while right < str_len:
            while s[right] != "%":
                right += 1

            num_len = int(s[left:right])
            start = right + 1
            word = s[start : start + num_len]
            result.append(word)

            left = start + num_len
            right = left

        return result

For larger inputs, encode can avoid rebuilding the accumulated string by collecting each encoded piece first and joining them once.

def encode(self, strs: list[str]) -> str:
    parts = []

    for s in strs:
        parts.append(f"{len(s)}%{s}")

    return "".join(parts)

This keeps the encoding work at O(L) because it avoids repeatedly copying the existing result.

Summary and reflection

This problem made me curious about the algorithms behind framing data in protocols such as HTTP. It is a mechanism I have used without thinking much about its origin, but connecting the algorithm problem to a separate study of encoding and decoding makes the idea easier to retain.

I did not come up with the length-prefixed solution immediately. I found it while reviewing the standard approach, worked through why it handles delimiters and empty strings, and enjoyed the problem more once that boundary rule became clear.