Skip to main content

271. Encode and Decode Strings

medium

Design an encoder and decoder for a list of arbitrary strings round-tripped over a single string channel. The trick: any delimiter you pick can show up in the input — so length-prefix instead.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings. Your algorithm should be generalized enough to work on any possible characters.

Constraints

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] contains any possible characters out of 256 valid ASCII characters.

Examples

Example 1

Input
dummy_input = ["Hello","World"]
Output
["Hello","World"]

Explanation: Machine 1 encodes ["Hello","World"] into some intermediate string. Machine 2 decodes that string back into ["Hello","World"].

Example 2

Input
dummy_input = [""]
Output
[""]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Pick a delimiter (like comma)? Doesn't work — the input could contain commas. Same for any single delimiter.

Hint 2

Use a length prefix: encode each string as '<length>#<content>'.

Hint 3

On decode, parse digits up to '#', read that many characters as the next string, then repeat.

Solution approach

Reveal approach

Length-prefix encoding. For each input string s, append str(len(s)) + '#' + s to the buffer. To decode, walk the buffer with a cursor: read characters until you hit '#' — those form the length L as a number; read the next L characters as the next string; advance the cursor past it; repeat until the buffer is exhausted. The '#' is unambiguous as the length delimiter because everything before it is guaranteed to be digits. Works for any 256-char alphabet, including empty strings and strings that contain '#'.

Complexity

Time
O(n) encode and decode
Space
O(n)

Related patterns

  • string-design

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Meta
  • Google

Practice these live with InterviewChamp.AI

Drill Encode and Decode Strings and Strings problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →