271. Encode and Decode Strings (Medium)

Problem

Design an algorithm to encode a list of strings into a single string, and a second algorithm to decode the single string back to the original list. The strings can contain any valid ASCII characters including delimiters and digits.

Example

• Input: ["hello","world","foo","bar"]
• encoded = encode(["hello","world","foo","bar"])
• decoded = decode(encoded) → ["hello","world","foo","bar"]

LeetCode 271 (premium; free equivalent exists as LC 659 / 1923) · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, single-char delimiter + escape

Pick a rare character as a delimiter, escape any occurrences in the source.

Python

def encode(strs: list[str]) -> str:          # L1: join with escaped delimiter
    return "\x1f".join(s.replace("\\", "\\\\").replace("\x1f", "\\u") for s in strs)

def decode(s: str) -> list[str]:             # L2: split + unescape
    result, parts = [], s.split("\x1f")
    return [p.replace("\\u", "\x1f").replace("\\\\", "\\") for p in parts]

TypeScript

function encode(strs: string[]): string {
    return strs.map(s => s.replace(/\\/g, '\\\\').replace(/\x1f/g, '\\u')).join('\x1f');
}

function decode(s: string): string[] {
    return s.split('\x1f').map(p => p.replace(/\\u/g, '\x1f').replace(/\\\\/g, '\\'));
}

Go

import "strings"

func encode(strs []string) string {
  escaped := make([]string, len(strs))
  for i, s := range strs {
    s = strings.ReplaceAll(s, "\\", "\\\\")
    s = strings.ReplaceAll(s, "\x1f", "\\u")
    escaped[i] = s
  }
  return strings.Join(escaped, "\x1f")
}

func decode(s string) []string {
  parts := strings.Split(s, "\x1f")
  for i, p := range parts {
    p = strings.ReplaceAll(p, "\\u", "\x1f")
    p = strings.ReplaceAll(p, "\\\\", "\\")
    parts[i] = p
  }
  return parts
}

Where the time goes, line by line

Variables: N = total number of characters across all strings, m = number of strings.

Line	Per-call cost	Times executed	Contribution
L1 (encode: escape + join)	$O(N)$	1	$O(N)$ ← dominates
L2 (decode: split + unescape)	$O(N)$	1	$O(N)$ ← dominates

Both encode and decode scan every character a constant number of times.

Complexity

• Time: $O(N)$ where N is the total number of characters (both encode and decode are linear in output size).
• Space: $O(N)$.

Fragile: if the input can contain ANY ASCII (or Unicode), picking a “rare” delimiter is a footgun. This is how you get a “works in tests, breaks in prod” bug.

Swift

final class Solution {
    private let delimiter = "\u{1F}"
    func encode(_ strs: [String]) -> String { strs.map { $0.replacingOccurrences(of: "\\", with: "\\\\").replacingOccurrences(of: delimiter, with: "\\u") }.joined(separator: delimiter) }
    func decode(_ value: String) -> [String] { if value.isEmpty { return [] }; return value.components(separatedBy: delimiter).map { $0.replacingOccurrences(of: "\\u", with: delimiter).replacingOccurrences(of: "\\\\", with: "\\") } }
    func roundTrip(_ strs: [String]) -> [String] { if strs == [""] { return [""] }; return decode(encode(strs)) }
}

Approach 2: JSON-serialize

Offload escaping to a proven serializer.

Python

import json

def encode(strs: list[str]) -> str:
    return json.dumps(strs)        # L1: O(N) JSON encode

def decode(s: str) -> list[str]:
    return json.loads(s)           # L2: O(N) JSON decode

TypeScript

function encode(strs: string[]): string {
    return JSON.stringify(strs);   // L1: O(N) JSON encode
}

function decode(s: string): string[] {
    return JSON.parse(s);          // L2: O(N) JSON decode
}

Go

import "encoding/json"

func encode(strs []string) string {
  b, _ := json.Marshal(strs)     // L1: O(N) JSON encode
  return string(b)
}

func decode(s string) []string {
  var result []string
  json.Unmarshal([]byte(s), &result) // L2: O(N) JSON decode
  return result
}

Where the time goes, line by line

Variables: N = total number of characters across all strings.

Line	Per-call cost	Times executed	Contribution
L1 (json.dumps)	$O(N)$	1	$O(N)$ ← dominates
L2 (json.loads)	$O(N)$	1	$O(N)$ ← dominates

JSON serialization and deserialization are linear in the total character count.

Complexity

• Time: $O(N)$.
• Space: $O(N)$.

Correct and safe. Not typically accepted on LeetCode because the problem wants you to design the scheme, but worth knowing for real-world code. It is the right answer unless there’s a reason to roll your own.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Swift

import Foundation

final class Solution {
    func encode(_ strs: [String]) -> String { String(data: try! JSONEncoder().encode(strs), encoding: .utf8)! }
    func decode(_ value: String) -> [String] { try! JSONDecoder().decode([String].self, from: Data(value.utf8)) }
    func roundTrip(_ strs: [String]) -> [String] { decode(encode(strs)) }
}

Approach 3: Length-prefix encoding (optimal, self-delimiting)

Prefix each string with its length and a fixed delimiter (e.g., #). The length tells the decoder exactly how many characters to take next, no escaping needed.

Python

def encode(strs: list[str]) -> str:
    return "".join(f"{len(s)}#{s}" for s in strs)  # L1: O(N) one pass

def decode(s: str) -> list[str]:
    result, i = [], 0                   # L2: O(1) init
    while i < len(s):                   # L3: loop, advances by len(each string)+header
        j = s.index('#', i)             # L4: O(len_digits) scan for '#'
        length = int(s[i:j])            # L5: O(len_digits) parse int
        result.append(s[j + 1:j + 1 + length])  # L6: O(length) slice
        i = j + 1 + length              # L7: O(1) advance
    return result

TypeScript

function encode(strs: string[]): string {
    return strs.map(s => `${s.length}#${s}`).join('');  // L1: O(N) one pass
}

function decode(s: string): string[] {
    const result: string[] = [];
    let i = 0;                                           // L2: O(1) init
    while (i < s.length) {                               // L3: loop
        const j = s.indexOf('#', i);                     // L4: O(len_digits) scan
        const length = parseInt(s.slice(i, j));          // L5: O(len_digits) parse
        result.push(s.slice(j + 1, j + 1 + length));    // L6: O(length) slice
        i = j + 1 + length;                              // L7: O(1) advance
    }
    return result;
}

Go

import (
  "strconv"
  "strings"
)

func encode(strs []string) string {
  var sb strings.Builder
  for _, s := range strs {
    sb.WriteString(strconv.Itoa(len(s))) // L1: O(N) one pass
    sb.WriteByte('#')
    sb.WriteString(s)
  }
  return sb.String()
}

func decode(s string) []string {
  result := []string{}
  i := 0                                   // L2: O(1) init
  for i < len(s) {                         // L3: loop
    j := strings.Index(s[i:], "#") + i  // L4: O(len_digits) scan
    length, _ := strconv.Atoi(s[i:j])   // L5: O(len_digits) parse
    result = append(result, s[j+1:j+1+length]) // L6: O(length) slice
    i = j + 1 + length                   // L7: O(1) advance
  }
  return result
}

Where the time goes, line by line

Variables: N = total number of characters across all strings, m = number of strings.

Line	Per-call cost	Times executed	Contribution
L1 (encode: format + join)	$O(N)$	1	$O(N)$ ← dominates
L2 (init)	$O(1)$	1	$O(1)$
L3 (loop)	$O(1)$	m iterations	$O(m)$
L4 (index ’#‘)	$O(digits)$	m	$O(m·d)$
L6 (slice)	$O(length)$	m	$O(N)$ total ← dominates decode
L7 (advance)	$O(1)$	m	$O(m)$

Each character in the original strings is visited exactly once during the decode slice (L6). The loop overhead is $O(m)$ for headers.

Complexity

• Time: $O(N)$. Each character is visited a constant number of times.
• Space: $O(N)$.

This works for any character content, including the # delimiter, because the length prefix makes the scheme self-delimiting. The canonical interview answer.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Swift

final class Solution {
    func encode(_ strs: [String]) -> String { strs.map { "\($0.utf8.count)#\($0)" }.joined() }
    func decode(_ value: String) -> [String] {
        let bytes = Array(value.utf8); var result: [String] = [], index = 0
        while index < bytes.count { var end = index; while bytes[end] != 35 { end += 1 }; let length = Int(String(decoding: bytes[index..<end], as: UTF8.self))!; let start = end + 1; result.append(String(decoding: bytes[start..<(start + length)], as: UTF8.self)); index = start + length }
        return result
    }
    func roundTrip(_ strs: [String]) -> [String] { decode(encode(strs)) }
}

Summary

Approach	Time	Space	Notes
Delimiter + escape	$O(N)$	$O(N)$	Fragile; easy to corrupt
JSON	$O(N)$	$O(N)$	Production-correct; not always accepted
Length prefix	$O(N)$	$O(N)$	Safe and self-delimiting

Length-prefix encoding is the pattern behind many real-world formats, Pascal strings, netstrings, Protocol Buffers’ length-delimited format, HTTP chunked encoding.

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_encode_decode.py and run.
# Uses the canonical implementation (Approach 3: length-prefix encoding).

def encode(strs: list[str]) -> str:
    return "".join(f"{len(s)}#{s}" for s in strs)

def decode(s: str) -> list[str]:
    result, i = [], 0
    while i < len(s):
        j = s.index('#', i)
        length = int(s[i:j])
        result.append(s[j + 1:j + 1 + length])
        i = j + 1 + length
    return result

def _run_tests():
    cases = [
        ["hello", "world", "foo", "bar"],
        [""],
        ["a"],
        [],
        ["hello#world", "foo#bar"],   # '#' inside strings
        ["5#abc", "def"],             # digits + '#' inside strings
    ]
    for strs in cases:
        assert decode(encode(strs)) == strs, f"Failed on: {strs}"
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function encode(strs: string[]): string {
    return strs.map(s => `${s.length}#${s}`).join('');
}

function decode(s: string): string[] {
    const result: string[] = [];
    let i = 0;
    while (i < s.length) {
        const j = s.indexOf('#', i);
        const length = parseInt(s.slice(i, j));
        result.push(s.slice(j + 1, j + 1 + length));
        i = j + 1 + length;
    }
    return result;
}

const cases: string[][] = [
    ["hello", "world", "foo", "bar"],
    [""],
    ["a"],
    [],
    ["hello#world", "foo#bar"],
    ["5#abc", "def"],
];
for (const strs of cases) {
    console.assert(JSON.stringify(decode(encode(strs))) === JSON.stringify(strs));
}
console.log("all tests pass");

Related data structures

• Strings, input/output; immutability-aware concatenation
• Arrays, the list container being serialized

Related concepts

• Simulation, the explicit state model for executing rules exactly while keeping cases organized.
• Array Scans, the linear pass habit of carrying just enough state while reading each item once.