Pattern visualizer

Encode and Decode Strings

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. Animated on: strs = ["hi", "a#b", "", "cat"] — encode the list into one string, then decode it back to exactly the same list..

Length prefix, so no character is ever reserved

time O(total characters) for both directionsspace O(total characters) for the encoded stringstep 1 / 11

[0]

a#b

[1]

(empty)

[2]

cat

[3]

line 1

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

Where to practice Strings

Practice Strings problems All Strings problems Back to roadmap