Domain 2MediumCORE

Encode and Decode Strings

We are tasked with implementing a serialization mechanism that converts a list of strings into a single encoded string and vice versa. The core requirement is lossless compression: decode(encode(strs)) must return exactly strs.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#String

271. Encode and Decode Strings

Model: qwen3.5:9b
Topics: String
FAANG asked: 0
Acceptance rate: 33.0%


Problem Breakdown

We are tasked with implementing a serialization mechanism that converts a list of strings into a single encoded string and vice versa. The core requirement is lossless compression: decode(encode(strs)) must return exactly strs.

Inputs: A vector/list of strings (vector<string> or Python List[str]). Outputs: An encoded string (for encoding) / List of strings (for decoding).

Constraints & Edge Cases to Consider:

  1. Empty Strings: The list can contain empty strings (""), and the input list itself is non-empty but individual elements might be null-length.
  2. Special Characters: Constraints specify “any possible characters out of 256 valid ASCII”. This means we cannot rely on standard delimiters like newlines \n, commas ,, or pipes | because they could appear in the data itself (e.g., a file path string containing /).
  3. Length Ambiguity: If I simply concatenate strings with a delimiter, and that delimiter exists in one of the strings, parsing fails. We need to know exactly where each string starts and ends without relying on delimiters present in the content.

Intuition

A naive approach is concatenating all strings separated by a unique character (e.g., |). However, since we are allowed any ASCII characters, our delimiter might be part of the data itself.

To solve this robustly, we need to encode metadata about each string’s length alongside its content so that the decoder knows exactly how many bytes/characters belong to one specific string before moving to the next.

Why simple concatenation fails: If strs = ["a", "b"], encoded as "ab". Decoder doesn’t know if it should split after 1 char or more. If we use a delimiter like \n and input is ["hello\nworld"], decoding breaks immediately.

Key Insight: We can encode the length of each string using a fixed-width integer representation (e.g., always 4 digits) followed by the raw content. By fixing the width of the header, we know exactly how many characters to read for the count before consuming that many characters as data. This makes the encoding scheme delimiter-free and robust against any character appearing in the payload.

Approach

  1. Encoding (encode):
    • Iterate through each string s.
    • Calculate its length len(s).
    • Format this length into a fixed-width integer (e.g., padded to 4 digits using zero-padding). This ensures the decoder knows exactly how many characters constitute the header.
    • Append the formatted length and then the raw string content directly to an accumulator buffer.
  2. Decoding (decode):
    • Initialize a pointer i = 0.
    • While there is data remaining in the encoded string:
      • Read exactly 4 characters from index i (the header). Convert this substring into an integer to get length.
      • Move the pointer forward by these 4 characters.
      • Extract a slice of length length starting at current i. This is one decoded string.
      • Add it to our result list and advance the main index past both header and content (i += 4 + length).

This approach guarantees that even if the data contains newlines, numbers, or other special characters, we can parse boundaries correctly because we trust the fixed-width header count rather than a delimiter.

Complexity Analysis

  • Time Complexity: O(N)O(N) where NN is the total number of characters in all strings combined (including headers). We iterate through each character exactly once during encoding and decoding operations are proportional to reading bytes/chars. The overhead for parsing 4-digit integers per string is constant relative to content size, so it remains linear with respect to input data volume.
  • Space Complexity: O(N)O(N) where NN represents the total characters in strs. We store an encoded string roughly equal in size to the original strings plus a small fixed overhead for length headers (4 bytes per string).

Solution

class Codec:
    def encode(self, strs):
        """Encodes a list of strings into one single string."""
        if not strs:
            return ""
        
        encoded_parts = []
        # Iterate through each string in the input list. 
        # We use 4 digits for length to ensure fixed-width parsing without delimiters.
        for s in strs:
            # Format length as a zero-padded integer (e.g., len=5 -> "0005")
            header = f"{len(s):0>4}"  
            encoded_parts.append(header)
            encoded_parts.append(s)
        
        return "".join(encoded_parts)

    def decode(self, s):
        """Decodes a single string back into the original list of strings."""
        if not s:
            return []
            
        decoded_strings = []
        i = 0
        
        while i < len(s):
            # Read exactly 4 characters for the length header. 
            # This works regardless of what content follows (e.g., newlines).
            try:
                length_str = s[i : i + 4]
                current_len = int(length_str)
                
                # Move index past the header to start reading actual string data
                i += 4
                
                # Extract the substring corresponding to this specific string's content
                decoded_strings.append(s[i : i + current_len])
                
                # Advance main pointer by length of content read
                i += current_len
            except ValueError:
                # Fallback or safety check, though logic guarantees valid header format
                break
                
        return decoded_strings

# Example usage for verification (not part of class definition)
codec = Codec()
print(codec.decode(codec.encode(["Hello", "World"]))) 

Edge Cases Handled

  • Empty Strings (""): The length is 0. Header becomes "0000". Decoder reads 4 chars, parses 0, extracts empty slice. Correctly handles consecutive or trailing empty strings in the list.
  • Special Characters (Newlines \n, Tabs \t): Since we do not use a delimiter like \n to separate items, and rely solely on length headers, these characters are treated as regular payload data within their respective string slices. They will be preserved exactly during decode.
  • Max Constraints: With strs[i].length <= 200, the header fits easily in standard integer types (4 digits covers up to 9999). The total encoded size remains linear with input constraints, preventing memory overflow for valid inputs.