Encode and Decode Strings
Asked at OpenAI
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.
Asked At
| 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.
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
class 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.