271. Encode and Decode Strings
Asked at OpenAI
Difficulty
Medium
Time
O(n)
Space
O(n)
Pattern
Array
Companies
1
Problem
Design two functions that work as a pair. encode takes a list of strings and turns it into one single string. decode takes that single string and rebuilds the exact same list of strings.
The strings can contain any of the 256 ASCII characters, including #, digits, commas, spaces and empty strings. So you cannot just join the strings with a separator like , — that separator might already appear inside one of the strings, and then decode would split in the wrong place.
Your format must be self-delimiting: the decoder must be able to tell where each string ends without guessing. A common trick is to write the length of each string first, then a marker character, then the string itself. For example, "hello" becomes "5#hello", and the decoder reads 5, skips the #, and takes the next 5 characters.
Return the encoded string from encode, and the original list from decode. The list decode(encode(strs)) returns must equal strs.
One string in, one string out
Constraints
- ●
1 <= strs.length <= 200 - ●
0 <= strs[i].length <= 200 - ●
strs[i] contains any of the 256 valid ASCII characters
Examples
strs = ["Hello","World"]["Hello","World"]strs = [""][""]strs = ["we","say",":"]["we","say",":"]Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| OpenAI | Medium | View all OpenAI questions → |
How to Think About It
Brute force: concatenate with a delimiter like ",". Fails if the delimiter appears in the input strings.
Use a length-prefix encoding: for each string, write its length followed by a separator (like #), then the string itself. Example: "hello" becomes "5#hello".
The decoding reads the number before #, then reads that many characters as the string. This avoids ambiguity regardless of string content.
Another approach: use a character-count prefix. For each string, encode the count of characters, then a delimiter, then the content. The delimiter must be unique.
A simpler variant: use a non-ASCII escape character or length encoding. The key insight is that you need a self-delimiting format.
Example: encode(["neet","code","love","you"]) -> "4#neet4#code4#love3#you". Decode reads 4, skips #, reads "neet", then 4, skips #, reads "code", etc.
Optimal Approach
Step 1: Encode: for each string s in the list, append len(s) + "#" + s to the result. This creates a self-delimiting format.
Step 2: The encoded string for ["hello","world"] is "5#hello5#world".
Step 3: Decode: start at index 0. Read characters until you find "#". The number before "#" is the length of the next string. Read that many characters after "#" as the string. Move the pointer forward and repeat.
Step 4: This works because the length prefix tells the decoder exactly how many characters to read, so no string content can confuse the decoder.
Step 5: Example walkthrough with ["we","say",":"]:
Encode: "2#we3#say1#:"
Decode: read "2" -> length 2, skip #, read "we". Read "3" -> length 3, skip #, read "say". Read "1" -> length 1, skip #, read ":". Result: ["we","say",":"].
Time: O(n) for both encode and decode where n is the total length of all strings. Space: O(n) for the encoded string.
Length prefix + # marker
What Trips People Up in Real Interviews
Using a simple delimiter like "," or "|" without considering that the delimiter might appear inside the strings.
Forgetting that the length prefix itself could be multi-digit. "12#hello world" needs to parse "12" as the length, not "1".
Not handling empty strings. An empty string "" encodes as "0#" and must decode back to "" correctly.
Using JSON or other serialization libraries without implementing the algorithm. Interviewers want to see the encoding logic, not a library call.
Not thinking about the edge case where strings contain the separator character (#). The length-prefix approach inherently handles this.
Solution Code
O(n) timeclass Codec:
def encode(self, strs: list[str]) -> str:
result = []
for s in strs:
result.append(str(len(s)) + '#' + s)
return ''.join(result)
def decode(self, s: str) -> list[str]:
result = []
i = 0
while i < len(s):
j = i
while s[j] != '#':
j += 1
length = int(s[i:j])
result.append(s[j + 1:j + 1 + length])
i = j + 1 + length
return resultFrequently Asked Questions
What is the Encode and Decode Strings problem?
Design an algorithm to encode a list of strings to a single string and decode it back. The encoding must handle arbitrary strings including special characters.
How do you solve Encode and Decode Strings?
The optimal approach runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Encode and Decode Strings?
Encode and Decode Strings is asked at OpenAI. It is a medium difficulty problem.
What are common mistakes on Encode and Decode Strings?
- Using a simple delimiter like "," or "|" without considering that the delimiter might appear inside the strings.
- Forgetting that the length prefix itself could be multi-digit. "12#hello world" needs to parse "12" as the length, not "1".
- Not handling empty strings. An empty string "" encodes as "0#" and must decode back to "" correctly.
- Using JSON or other serialization libraries without implementing the algorithm. Interviewers want to see the encoding logic, not a library call.
- Not thinking about the edge case where strings contain the separator character (#). The length-prefix approach inherently handles this.