Encode and Decode Strings

Convert a list of any strings into one string and recover the exact list.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Encode and Decode Strings: A decimal length before # makes each payload boundary explicit, even when the payload contains # or is empty.

Input and goalConvert a list of any strings into one string and recover the exact list.

Encode lintThe first input string has length 4, so encoding emits 4#lint.

encode item 0lint0#1""2

emitted4#lint

Recognize it

Arbitrary strings, including empty strings and delimiter characters, must be concatenated and later recovered without escaping ambiguity.

Keep true

At the start of each decode loop, index points to the first decimal length digit. After locating # and consuming exactly length payload characters, index points to the next length or end of data.

Reuse it

Prefix variable-length records with a parseable size so payload bytes remain opaque; this framing pattern transfers to network protocols, file formats, and binary serialization.

Pattern: Length prefix.

Simple idea: Save each string as length#text. The decoder reads the length first, so the text may contain any character, including #.

def encode_strings(strings: list[str]) -> str:
   return "".join(f"{len(text)}#{text}" for text in strings)


def decode_strings(data: str) -> list[str]:
   strings = []
   index = 0

   while index < len(data):
      separator = data.index("#", index)
      length = int(data[index:separator])
      index = separator + 1
      strings.append(data[index : index + length])
      index += length
   return strings

Cost: $O(n)$ time and $O(n)$ output space.