Encode and Decode Strings

Length prefix, so no character is ever reserved

time O(total characters) for both directionsspace O(total characters) for the encoded string

The instinct is to join with a separator, and it fails the moment a payload contains that separator — there is no character you can reserve, because the input is arbitrary. The fix is to stop marking boundaries and start counting: write each string as its length, a '#' to say where the length stops, then the raw bytes. The decoder reads a number, jumps exactly that far, and never has to interpret the payload at all — so a '#' inside a string is just data, and an empty string is still a real entry.

Details

Animated on: strs = ["hi", "a#b", "", "cat"] — encode the list into one string, then decode it back to exactly the same list.

Problem:Encode and Decode StringsMedium

Length prefix, so no character is ever reserved

step 1 / 11

[0]

a#b

[1]

(empty)

[2]

cat

[3]

4 strings have to survive a round trip through ONE flat string. Any separator you pick can also appear inside a payload — "a#b" already contains a '#' — so the join has to carry a count, not just a mark.

Pseudocode

1FUNCTION encode(strs)
2  out <- ""
3  FOR k <- 0 TO LENGTH(strs) - 1
4    out <- out + LENGTH(strs[k]) + "#" + strs[k]
5  RETURN out
6FUNCTION decode(s)
7  res <- EMPTY LIST
8  i <- 0
9  WHILE i < LENGTH(s)
10    j <- INDEX OF "#" IN s FROM i
11    n <- NUMBER(s[i .. j - 1])
12    APPEND s[j + 1 .. j + n] TO res
13    i <- j + 1 + n
14  RETURN res

← / → step · space play · Home restart

Every step in words

Show all 11 steps

4 strings have to survive a round trip through ONE flat string. Any separator you pick can also appear inside a payload — "a#b" already contains a '#' — so the join has to carry a count, not just a mark.
"hi" is 2 characters, so it is written as "2#hi" — the count first, then a '#' to say where the count stops. Encoded so far: "2#hi".
"a#b" holds a '#' of its own, which is exactly the input a plain join breaks on. Length-prefixing does not care: it becomes "3#a#b", and the decoder will be told to take 3 characters whatever they are.
The empty string still gets a header, "0#". Without one it would leave no trace at all and the decoder would hand back 3 strings instead of 4.
"cat" is 3 characters, so it is written as "3#cat" — the count first, then a '#' to say where the count stops. Encoded so far: "2#hi3#a#b0#3#cat".
All 4 strings are now the single 16-character string "2#hi3#a#b0#3#cat". It reads as gibberish on purpose: only a cursor knows which '#' is a header and which is payload, and the cursor is never wrong because each header tells it exactly how far to jump.
Cursor sits at 0. Scan to the first '#' at 1: the digits before it read "2", so the next 2 characters s[2..3] = "hi" are one whole string. Cursor jumps to 4, never re-reading a character.
Digits "3" say take 3, so s[6..8] = "a#b" comes back whole — including the '#' sitting at index 7 inside it. A decoder that searched for the next '#' would have stopped there and split one string into two.
Digits "0" say take 0 characters, so nothing is consumed and the empty string is recovered exactly. The cursor still steps past the 2-character header to 11.
Cursor sits at 11. Scan to the first '#' at 12: the digits before it read "3", so the next 3 characters s[13..15] = "cat" are one whole string. Cursor jumps to 16, never re-reading a character.
The cursor reached 16, the end of the encoded string, having read every character exactly once. 4 strings recovered, identical to the originals — the empty one and the embedded '#' included.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Encode and Decode Strings in the editor All Strings problems Back to roadmap