Unpack a Length-Prefixed Stream
MediumArrays & Hashing
Problem
A messaging service sends a list of strings as one string. Each item is written as its length in decimal, then the character #, then the item itself. For example ["abc", "", "1#"] becomes "3#abc0#2#1#".
Items may contain any printable character, including # and digits. Given a valid stream, return the original list of items.
Example 1
- Input:
- stream = "3#abc0#2#1#"
- Output:
- ["abc", "", "1#"]
Read 3 → take 'abc'; read 0 → empty item; read 2 → take '1#'.
Example 2
- Input:
- stream = "5#hello5#world"
- Output:
- ["hello", "world"]
Example 3
- Input:
- stream = ""
- Output:
- []
An empty stream encodes an empty list.
Constraints
- 0 ≤ stream.length ≤ 10^5
- The stream is a valid encoding.
- Item lengths fit in a 32-bit integer.
Hint
Show the first hint
Why is splitting on '#' wrong here?
Walkthrough
How to approach it
01Clarify before coding
- Can items contain '#' or digits? Yes, which is why the length prefix exists.
- Can an item be empty? Yes, encoded as '0#'.
- Is the input always valid? Yes, no error handling is needed.
02Brute force
Split the stream on '#' and try to stitch pieces back together.
Cost: It is not just slow, it is wrong: '#' inside an item makes the split ambiguous, and repairing it needs backtracking.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.