Encode and Decode Strings

Encode and Decode Strings asks you to turn a list of strings into one string and back again — losslessly. The catch is that the strings can contain any characters, including whatever separator you might be tempted to use. The fix is a classic framing trick: prefix each string with its length.

The slow way first

The tempting idea is to join the strings with a separator like a comma: "hi,you". But what if a string contains a comma? Then decode cannot tell a real comma apart from a separator. You could try escaping every special character, but that gets fiddly and bug-prone fast — and there is no character that is guaranteed never to appear in the input.

The question to ask: how do I mark where each string ends without relying on its contents? Instead of a separator that lives between strings, attach metadata that says exactly how long the next string is.

The idea: length-prefix framing

Encode each string as len(s) + "#" + s. The number tells the decoder exactly how many characters to read, so the contents of the string never matter — even if the string itself contains a #.

The # only ever separates the number from the string — and a number is always plain digits, so the first # we hit is unambiguous. After reading the length, we trust the count, not any character inside the string.

Walk through it

Step through the animation. The pointer i scans the encoded buffer "2#hi3#you". It reads digits until the first # to learn the length is 2, skips the #, then takes the next 2 characters ("hi"). It jumps the pointer forward and repeats: length 3, take "you". When the pointer reaches the end, the result list is complete.

Pseudocode

encode: for each string s, append str(len(s)) + "#" + s
decode:
    i = 0
    while i is not past the end of s:
        j = i
        while s[j] is not "#":      # scan the length digits
            j += 1
        length = the integer in s[i:j]
        take the length characters starting at j + 1
        i = j + 1 + length          # jump past the string we just read
    return the collected strings

The Python solution

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

• result collects the decoded strings; i is where the next length-prefixed chunk begins.
• The inner while s[j] != "#" scans forward over the digits until it finds the # marker.
• int(s[i:j]) parses those digits — the slice from i up to the # — into the length number.
• s[j + 1 : j + 1 + length] takes exactly length characters starting right after the #. This is why the string contents never matter: we count, we do not search.
• i = j + 1 + length jumps the pointer past the chunk we just decoded so the loop reads the next one.

(The matching encode is one line: "".join(str(len(x)) + "#" + x for x in strs).)

Complexity

Both directions are linear in the total number of characters. The space is the output itself — the encoded string or the decoded list.

When this pattern shows up

Practice