DSAPrep
MediumArrays & Hashing

Encode and Decode Strings

Design an algorithm to encode a list of strings into a single string. The encoded string is sent over a network and decoded back into the original list of strings.

Implement encode and decode so that decode(encode(strs)) always reconstructs the original list exactly, no matter what characters the strings contain (including commas, slashes, or other characters you might otherwise be tempted to use as a separator).

Example 1

Input: strs = ["lint","code","love","you"]
Output: ["lint","code","love","you"]
Explanation: encode(strs) produces one string that decode() parses back into the exact original list.

Example 2

Input: strs = [""]
Output: [""]

Constraints

  • 0 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] can contain any valid ASCII character.
View original on LeetCode ↗

This isn’t really an efficiency problem — any reasonable approach is linear. The real challenge is correctness: whatever separator you pick between strings, one of the input strings might legally contain that exact separator, and your decoder has no way to tell “end of string” from “this string just happens to contain a comma.”

Delimiter Join (Broken)

Time O(n)Space O(n)

The obvious first idea: join the strings with a separator like a comma, and split on that separator to decode.

class Codec:
    def encode(self, strs: list[str]) -> str:
        return ",".join(strs)


    def decode(self, s: str) -> list[str]:
        return s.split(",")

This looks fine until a string contains the separator itself:

encode(["a,b", "c"])   # -> "a,b,c"
decode("a,b,c")        # -> ["a", "b", "c"]   -- wrong! Original had 2 strings, not 3.

The encoding is ambiguous — "a,b,c" could have come from ["a,b", "c"], ["a", "b,c"], or ["a", "b", "c"]. No amount of escaping the comma fully closes this hole without extra bookkeeping, so this approach is discarded rather than optimized.

Length-Prefix Encoding

OptimalTime O(n)Space O(n)

Instead of relying on a separator that might collide with the data, prefix each string with its own length followed by a delimiter (any character not used as a digit, e.g. /). Since we know exactly how many characters to read once we know the length, the content of the string — commas, slashes, anything — can never be misread as structure.

class Codec:
    def encode(self, strs: list[str]) -> str:
        encoded = ""
        for s in strs:
            encoded += str(len(s)) + "/" + s
        return encoded


    def decode(self, s: str) -> list[str]:
        result = []
        i = 0
        while i < len(s):
            slash = s.find("/", i)
            length = int(s[i:slash])
            start = slash + 1
            result.append(s[start:start + length])
            i = start + length
        return result

Tracing decode("2/ab2/cd"), which came from encode(["ab", "cd"]):

i
2
0
/
1
a
2
b
3
2
4
/
5
c
6
d
7
1 / 6
comparingresultcurrent

At i=0, scan forward for the next / to find the length prefix.

Correctness: the length prefix tells the decoder precisely how many characters belong to the current string, so it never has to guess where a string ends by scanning its contents — the string’s own characters, whatever they are, can never be confused with a delimiter.

Complexity: encoding writes each character of every string exactly once, plus a small fixed-size prefix per string — O(n) time and space, where n is the total number of characters across all strings. Decoding does the same work in reverse — one pass, O(n) time, building an output list that also totals O(n) space.