ASAPUtils
The signal
This is a design problem rather than an algorithms one, and the entire difficulty is in one sentence of the constraints: the strings may contain any characters. That kills the first idea everyone has, and noticing why is the whole exercise.
Approach ladder
1. Join with a delimiter — broken
strs.join(',') then split(','). It works right up until an input string contains a comma. Try
["a,b", "c"]: you encode "a,b,c" and decode ["a", "b", "c"]. Silently wrong.
Every delimiter has this problem. There is no character you can pick that the input is guaranteed not to contain.
2. Escape the delimiter — works, but fragile
Replace , with \, and \ with \\ before joining, then unescape. Correct, but now you have
two encodings to keep in sync and a decoder that must track escape state. It’s more code and more
bugs than the real answer.
3. The insight
The problem is that you’re asking the decoder to find where each string ends by inspecting the content. Stop doing that. Tell it the length up front, and it never needs to look at the content at all.
4. Optimal — length prefix
Encode each string as <length>#<string>. The decoder reads digits until #, converts them to a
number L, then takes exactly the next L characters — whatever they are, # included.
string encode(vector<string>& strs) {
string res;
for (string& s : strs) res += to_string(s.size()) + "#" + s;
return res;
}
vector<string> decode(string s) {
vector<string> res;
int i = 0;
while (i < (int)s.size()) {
int j = i;
while (s[j] != '#') j++; // read the digits
int len = stoi(s.substr(i, j - i));
res.push_back(s.substr(j + 1, len)); // take exactly len chars
i = j + 1 + len;
}
return res;
}
function encode(strs) {
return strs.map(s => s.length + '#' + s).join('');
}
function decode(s) {
const res = [];
let i = 0;
while (i < s.length) {
let j = i;
while (s[j] !== '#') j++; // read the digits
const len = Number(s.slice(i, j));
res.push(s.slice(j + 1, j + 1 + len)); // take exactly len chars
i = j + 1 + len;
}
return res;
}
Why the # is safe even though strings can contain #
Because it’s only ever read before a payload, never searched for inside one. The scan for #
starts at a known digit boundary and stops at the first non-digit. Once len is known, the decoder
consumes blindly. The content is never interpreted, so it can contain anything.
Complexity
- Time O(n) for both directions, where n is the total number of characters.
- Space O(n) for the output.
Traps
- Testing only with well-behaved input. Your test cases must include a string containing
#, a string containing a digit, an empty string, and an empty list. - Empty strings.
""encodes to"0#"and decodes back correctly — verify it, because a delimiter-based approach quietly loses them. - Off-by-one after the payload. The next index is
j + 1 + len, notj + len. - Building the encoded string with
+=in a JavaScript loop. Usemapandjoin.
Blank re-solve prompt
Design encode(list) and decode(string) for a list of arbitrary strings. Your test cases must include a string that contains your own delimiter.