271. Encode and Decode Strings

At a Glance

• Topic: arrays-hashing
• Pattern: String Encoding
• Difficulty: Medium
• Companies: Amazon, Meta, Google, Microsoft, Bloomberg
• Frequency: Medium
• LeetCode: 271

Problem (one-liner)

Design encode and decode so that a list of arbitrary strings (including empty, with delimiters inside) round-trips through a single flat string without ambiguity.

Recognition Cues

• "Serialize list of strings", "delimiter may appear inside strings"
• Need length-prefix or escape protocol (not naive join(','))

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute force — delimiter that cannot appear — fails if charset unconstrained.
• Better — escape delimiter characters — fragile and slow.
• Optimal — length prefix: len + '#' + payload repeated — O(total chars) encode/decode.

Optimal Solution

Go

package main

import "strconv"

type Codec struct{}

func (codec *Codec) Encode(words []string) string {
	var encoded string
	for _, word := range words {
		encoded += strconv.Itoa(len(word)) + "#" + word
	}
	return encoded
}

func (codec *Codec) Decode(encoded string) []string {
	var words []string
	position := 0
	for position < len(encoded) {
		length := 0
		for encoded[position] != '#' {
			length = length*10 + int(encoded[position]-'0')
			position++
		}
		position++
		words = append(words, encoded[position:position+length])
		position += length
	}
	return words
}

JavaScript

class Codec {
	encode(words) {
		let encoded = '';
		for (const word of words) {
			encoded += `${word.length}#${word}`;
		}
		return encoded;
	}

	decode(encoded) {
		const words = [];
		let position = 0;
		while (position < encoded.length) {
			let delimiterIndex = position;
			while (encoded[delimiterIndex] !== '#') {
				delimiterIndex++;
			}
			const length = Number(encoded.slice(position, delimiterIndex));
			const start = delimiterIndex + 1;
			words.push(encoded.slice(start, start + length));
			position = start + length;
		}
		return words;
	}
}

Walkthrough

Input words: ["hello", "5#world"]

Decode reads digit run → # → consume exactly length bytes.

Invariant: after reading length, the next length bytes are opaque payload.

Edge Cases

• Empty string in list — segment 0#.
• Empty list — empty encoded string.
• Very long strings — length fits in problem constraints / use big enough integer parsing.

Pitfalls

• Using a single character delimiter without escaping.
• Parsing length: stop at #, not fixed width.

Similar Problems

• 238. Product of Array Except Self — careful indexing.
• 242. Valid Anagram — string as structured data.
• 394. Decode String — nested encoding (cross-topic).

Variants

• Binary blobs with base64 length headers.
• Compression before length-prefix framing.

Mind-Map Tags

#strings #encoding #length-prefix #serialization #design