Encode and Decode Strings

PracticeNeetCode ↗LeetCode ↗

Design an algorithm to encode a list of strings into a single string, and decode that string back into the original list. The strings may contain any characters, including digits and whatever delimiter you choose.

Example

Key Pointers

• A plain delimiter (comma, etc.) is ambiguous if the strings themselves can contain that character — length-prefixing sidesteps that entirely.
• The separator after the length (#) only needs to not be a digit; it doesn't need to be rare, because it's never searched for inside the payload itself.
• Decoding never scans the string content to find boundaries — it always knows exactly how many characters to consume next.

Step-by-Step Analysis

1. Encode: for each string s, append len(s), then "#", then s itself, to a growing result string.
2. Decode: start at i = 0.
3. Scan forward from i to find the next "#", parse the digits before it as the length.
4. Read exactly length characters after the "#" as the next decoded string, advance i past it, and repeat.

Complexity

Time: O(n) total characters — Space: O(n)

Code

def encode(strs: list[str]) -> str:
    encoded = ""
    for s in strs:
        encoded += str(len(s)) + "#" + s
    return encoded

def decode(s: str) -> list[str]:
    result = []
    i = 0
    while i < len(s):
        j = i
        while s[j] != "#":
            j += 1
        length = int(s[i:j])
        result.append(s[j + 1 : j + 1 + length])
        i = j + 1 + length
    return result

Code Explanation

How the solution above works, piece by piece.

1. encode: for each string write len(s), a #, then the string itself. The result for the example is 4#lint4#code4#love3#you.
2. decode keeps a position i at the start of the next length prefix.
3. Move j forward to the next #; int(s[i:j]) is the length. Lengths can have several digits (e.g. 12#…), which is why we scan to # instead of reading one character.
4. s[j + 1 : j + 1 + length] is the word. It is cut by count, so any # inside it is just data.
5. i = j + 1 + length jumps straight to the next prefix. Both functions are O(total characters).

Visual Walkthrough

Decoding "4#lint4#code4#love3#you":

Video Explanation

NeetCode — Encode and Decode Strings, LeetCode 271