Approach Summary
Encode a list of strings into a single string using length-prefix encoding (length + delimiter + content, e.g. "4#lint4#code"). Decode by parsing the length prefix.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Multi-Character Delimiter Token | O(N) | O(1) auxiliary | Append a unique separator string (e.g. ":;") between elements. |
| 2 Approach 2: Length-Prefix Chunking (Optimal) | O(N) | O(1) auxiliary | Encode each string with its byte length followed by "#", guaranteeing collision-free decoding. |
Step 1: Baseline
Approach 1: Multi-Character Delimiter Token
Time: O(N)
Space: O(1) auxiliary
Join the strings using a designated delimiter such as ":;". During decoding, split the string using this delimiter. While intuitive, this approach requires the assumption that the delimiter cannot occur within the original strings themselves.
Approach 1: Multi-Character Delimiter Token Implementation
Approach 1: Multi-Character Delimiter Token
public class Codec {
public String encode(List<String> strs) {
StringBuilder sb = new StringBuilder();
for (String str : strs) {
sb.append(str).append(":;");
}
return sb.toString();
}
public List<String> decode(String s) {
List<String> result = new ArrayList<>();
if (s.isEmpty()) return result;
String[] parts = s.split(":;", -1);
for (int i = 0; i < parts.length - 1; i++) {
result.add(parts[i]);
}
return result;
}
}class Codec {
public:
string encode(vector<string>& strs) {
string encodedStr;
for (const auto& str : strs) {
encodedStr += str + ":;";
}
return encodedStr;
}
vector<string> decode(string s) {
vector<string> result;
size_t pos = 0;
string delimiter = ":;";
while ((pos = s.find(delimiter)) != string::npos) {
result.push_back(s.substr(0, pos));
s.erase(0, pos + delimiter.length());
}
return result;
}
};class Codec:
def encode(self, strs: list[str]) -> str:
return ":;".join(strs)
def decode(self, s: str) -> list[str]:
if not s:
return []
return s.split(":;")class Codec {
encode(strs) {
return strs.join(":;");
}
decode(s) {
if (s === "") return [];
return s.split(":;");
}
} Step 2: Most Optimized
Approach 2: Length-Prefix Chunking (Optimal)
Time: O(N)
Space: O(1) auxiliary
For every string, write `<length>#<string>`. During decoding, read the digits from the current pointer up to "#". Parse this number as integer `L`. The next `L` characters are guaranteed to belong strictly to the current string, regardless of whether they contain "#", quotes, or null bytes. Then move the pointer forward by `L` and repeat. This is the optimal stateless protocol.
Approach 2: Length-Prefix Chunking (Optimal) Implementation
Approach 2: Length-Prefix Chunking (Optimal)
public class Codec {
public String encode(List<String> strs) {
StringBuilder sb = new StringBuilder();
for (String str : strs) {
sb.append(str.length()).append('#').append(str);
}
return sb.toString();
}
public List<String> decode(String s) {
List<String> result = new ArrayList<>();
int i = 0;
while (i < s.length()) {
int hashIndex = s.indexOf('#', i);
int length = Integer.parseInt(s.substring(i, hashIndex));
result.add(s.substring(hashIndex + 1, hashIndex + 1 + length));
i = hashIndex + 1 + length;
}
return result;
}
}class Codec {
public:
string encode(vector<string>& strs) {
string encoded = "";
for (const string& s : strs) {
encoded += to_string(s.length()) + "#" + s;
}
return encoded;
}
vector<string> decode(string s) {
vector<string> result;
int i = 0, n = s.length();
while (i < n) {
int hashPos = s.find('#', i);
int length = stoi(s.substr(i, hashPos - i));
result.push_back(s.substr(hashPos + 1, length));
i = hashPos + 1 + length;
}
return result;
}
};class Codec:
def encode(self, strs: list[str]) -> str:
return "".join(f"{len(s)}#{s}" for s in strs)
def decode(self, s: str) -> list[str]:
res, i = [], 0
while i < len(s):
j = s.find('#', i)
length = int(s[i:j])
res.append(s[j + 1 : j + 1 + length])
i = j + 1 + length
return resclass Codec {
encode(strs) {
let result = "";
for (const str of strs) {
result += str.length + "#" + str;
}
return result;
}
decode(s) {
const result = [];
let i = 0;
while (i < s.length) {
const hashIndex = s.indexOf("#", i);
const length = parseInt(s.substring(i, hashIndex), 10);
result.push(s.substring(hashIndex + 1, hashIndex + 1 + length));
i = hashIndex + 1 + length;
}
return result;
}
}Edge Cases to Watch
- Empty list of strings (encoded into empty string, decoded into empty list)
- List containing empty strings (e.g. ["", ""] -> "0#0#")
- Strings containing delimiter characters, spaces, punctuation, or numbers (e.g. "4#code")
- Strings with non-ASCII or Unicode characters
Algorithmic Pattern
View Pattern Guide →
Master the Two Pointers Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Two Pointers pattern.
Framework: Two Pointers • Interview Prep: Tested at FAANG •
Explore all Two Pointers problems & invariants →
How to Recognize This Pattern
- Stateless serialization and deserialization of arbitrary string arrays
- Handling strings with embedded delimiters or non-ASCII characters
Complexity Analysis
Time Complexity
O(N)
Space Complexity
O(1)
Tags
Array String Design
Frequently Asked Questions
What is the optimal time and space complexity for Encode and Decode Strings?
The optimal solution for Encode and Decode Strings achieves O(N) runtime complexity and requires O(1) auxiliary space. Encoding iterates through all characters across all strings in O(N) time. Decoding reads the length prefix and slices the exact chunk in O(N) time. Auxiliary space is O(1) beyond the output buffer.
How do I identify that Encode and Decode Strings requires the Two Pointers pattern?
In technical interviews, look for key problem signals: Stateless serialization and deserialization of arbitrary string arrays; Handling strings with embedded delimiters or non-ASCII characters. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Two Pointers strategy.
What critical edge cases must be handled in Encode and Decode Strings?
Essential edge cases to verify include: Empty list of strings (encoded into empty string, decoded into empty list); List containing empty strings (e.g. ["", ""] -> "0#0#"); Strings containing delimiter characters, spaces, punctuation, or numbers (e.g. "4#code"); Strings with non-ASCII or Unicode characters. Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Encode and Decode Strings?
Encode and Decode Strings is a Medium-difficulty question tagged with medium recurrence. It is actively asked in technical screening and onsite interview loops at Google, Facebook, Amazon, Microsoft.