String Encoding and Decoding Patterns

Encoding and decoding problems ask you to transform data from one representation to another and back again. They test your ability to design protocols, handle edge cases, and work with stacks for nested structures. These problems are common in system design interviews (serialization) and coding interviews (string manipulation).

The unifying theme: every encoding must be unambiguous. Given the encoded output, the decoder must produce exactly one result.

1. Encode and decode strings (LeetCode 271)

Design an algorithm to encode a list of strings into a single string and decode it back. The strings can contain any character, including delimiters.

The length-prefix approach

The cleanest solution: prefix each string with its length and a delimiter character. This handles strings containing any characters, including the delimiter itself.

class Codec:
    """Encode/decode a list of strings using length-prefix protocol."""

    def encode(self, strs: list) -> str:
        """Encode list of strings to a single string. O(n) time."""
        encoded = []
        for s in strs:
            encoded.append(f"{len(s)}#{s}")
        return ''.join(encoded)

    def decode(self, s: str) -> list:
        """Decode a single string back to list. O(n) time."""
        result = []
        i = 0
        while i < len(s):
            # Find the '#' delimiter
            j = i
            while s[j] != '#':
                j += 1
            length = int(s[i:j])
            # Extract the string of that length
            result.append(s[j + 1:j + 1 + length])
            i = j + 1 + length
        return result

Example:

• Input: ["hello", "world"]
• Encoded: "5#hello5#world"
• Decoded: ["hello", "world"]

Why length-prefix works: The length tells us exactly how many characters to read after the #. Even if the string itself contains # or digits, we know exactly where it ends.

Time complexity: O(n) where n is the total length of all strings combined. Space complexity: O(n) for the encoded string.

Alternative: Escape character approach

Another strategy is to use an escape character. This is how many real protocols work:

class CodecEscape:
    """Encode/decode using escape characters."""

    def encode(self, strs: list) -> str:
        """Use '/' as escape: '/' -> '//', ',' -> '/,'. Separate with ','."""
        encoded = []
        for s in strs:
            escaped = s.replace('/', '//').replace(',', '/,')
            encoded.append(escaped)
        return ','.join(encoded)

    def decode(self, s: str) -> list:
        """Decode escaped string back to list."""
        result = []
        current = []
        i = 0
        while i < len(s):
            if s[i] == '/' and i + 1 < len(s):
                # Escaped character — take the next char literally
                current.append(s[i + 1])
                i += 2
            elif s[i] == ',':
                # Unescaped comma — string boundary
                result.append(''.join(current))
                current = []
                i += 1
            else:
                current.append(s[i])
                i += 1
        result.append(''.join(current))  # Don't forget the last string
        return result

The length-prefix approach is generally preferred in interviews because it’s simpler and doesn’t require scanning for escape sequences.

2. Run-length encoding

Run-length encoding (RLE) compresses consecutive identical characters into a count and character pair. “aaabbbcc” becomes “3a3b2c”.

Encoding

def run_length_encode(s: str) -> str:
    """Run-length encode a string. O(n) time, O(n) space."""
    if not s:
        return ""

    encoded = []
    count = 1

    for i in range(1, len(s)):
        if s[i] == s[i - 1]:
            count += 1
        else:
            encoded.append(f"{count}{s[i - 1]}")
            count = 1

    # Don't forget the last run
    encoded.append(f"{count}{s[-1]}")
    return ''.join(encoded)

Decoding

def run_length_decode(s: str) -> str:
    """Decode a run-length encoded string. O(n) time."""
    decoded = []
    i = 0

    while i < len(s):
        # Parse the number
        j = i
        while j < len(s) and s[j].isdigit():
            j += 1
        count = int(s[i:j])
        char = s[j]
        decoded.append(char * count)
        i = j + 1

    return ''.join(decoded)

Example:

• “aaabbbcc” encodes to “3a3b2c”
• “3a3b2c” decodes to “aaabbbcc”

When RLE doesn’t help

RLE only compresses strings with long runs of identical characters. For “abcdef”, the encoding “1a1b1c1d1e1f” is actually longer! In practice, RLE is used for binary images, simple graphics, and specific data formats.

3. Decode string (LeetCode 394)

Given an encoded string like "3[a2[c]]", decode it. The rule: k[encoded_string] means repeat encoded_string k times. This can be nested.

• "3[a]" becomes "aaa"
• "3[a2[c]]" becomes "accaccacc"
• "2[abc]3[cd]ef" becomes "abcabccdcdcdef"

Stack approach

Use a stack to handle nesting. When we see [, push the current state onto the stack. When we see ], pop and combine:

def decode_string(s: str) -> str:
    """Decode nested bracket string. O(n * max_k) time, O(n) space."""
    stack = []
    current_string = []
    current_num = 0

    for char in s:
        if char.isdigit():
            current_num = current_num * 10 + int(char)
        elif char == '[':
            # Save current state and start fresh
            stack.append((''.join(current_string), current_num))
            current_string = []
            current_num = 0
        elif char == ']':
            # Pop previous state and repeat current string
            prev_string, repeat_count = stack.pop()
            current_string = list(prev_string + ''.join(current_string) * repeat_count)
        else:
            current_string.append(char)

    return ''.join(current_string)

**Walkthrough with "3[a2[c]]":

Step	char	current_num	current_string	stack
0	3	3	[]	[]
1	[	0	[]	[("", 3)]
2	a	0	[“a”]	[("", 3)]
3	2	2	[“a”]	[("", 3)]
4	[	0	[]	[("", 3), (“a”, 2)]
5	c	0	[“c”]	[("", 3), (“a”, 2)]
6	]	0	[“a”, “c”, “c”]	[("", 3)]
7	]	0	[“a”, “c”, “c”, “a”, “c”, “c”, “a”, “c”, “c”]	[]

Result: “accaccacc”

Recursive approach

We can also solve this recursively, treating each k[...] as a sub-problem:

def decode_string_recursive(s: str) -> str:
    """Decode using recursion. O(n * max_k) time."""
    index = 0

    def decode():
        nonlocal index
        result = []

        while index < len(s) and s[index] != ']':
            if s[index].isdigit():
                # Parse number
                num = 0
                while index < len(s) and s[index].isdigit():
                    num = num * 10 + int(s[index])
                    index += 1
                index += 1  # Skip '['
                decoded = decode()  # Recurse
                index += 1  # Skip ']'
                result.append(decoded * num)
            else:
                result.append(s[index])
                index += 1

        return ''.join(result)

    return decode()

Time complexity: O(n * max_k) where max_k is the maximum repeat count. In the worst case, deeply nested strings can expand exponentially, but for typical inputs the total output length bounds the runtime. Space complexity: O(n) for the stack or recursion depth.

4. String compression (LeetCode 443)

Given an array of characters, compress it in-place using RLE. Single characters stay as-is, runs become the character followed by the count digits.

def compress(chars: list) -> int:
    """Compress character array in-place. O(n) time, O(1) space."""
    write = 0  # Write pointer
    read = 0   # Read pointer

    while read < len(chars):
        char = chars[read]
        count = 0

        # Count consecutive characters
        while read < len(chars) and chars[read] == char:
            read += 1
            count += 1

        # Write the character
        chars[write] = char
        write += 1

        # Write the count (only if > 1)
        if count > 1:
            for digit in str(count):
                chars[write] = digit
                write += 1

    return write

Example:

• ["a","a","b","b","c","c","c"] becomes ["a","2","b","2","c","3"], returns 6
• ["a"] stays ["a"], returns 1
• ["a","b","b","b","b","b","b","b","b","b","b","b","b"] becomes ["a","b","1","2"], returns 4

Key details:

• The count must be written as individual digit characters, not a single number.
• Single characters (count = 1) don’t get a count written.
• Must modify the array in-place and return the new length.

Time complexity: O(n) — single pass with two pointers. Space complexity: O(1) — everything is done in-place.

5. Serialize and deserialize binary tree (LeetCode 297)

This is a classic design problem. Encode a binary tree to a string and decode it back.

Preorder traversal with null markers

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class TreeCodec:
    """Serialize/deserialize binary tree using preorder traversal."""

    def serialize(self, root: TreeNode) -> str:
        """Encode tree to string. O(n) time and space."""
        tokens = []

        def preorder(node):
            if node is None:
                tokens.append("N")
                return
            tokens.append(str(node.val))
            preorder(node.left)
            preorder(node.right)

        preorder(root)
        return ','.join(tokens)

    def deserialize(self, data: str) -> TreeNode:
        """Decode string to tree. O(n) time and space."""
        tokens = iter(data.split(','))

        def build():
            val = next(tokens)
            if val == "N":
                return None
            node = TreeNode(int(val))
            node.left = build()
            node.right = build()
            return node

        return build()

Example:

• Tree: [1, 2, 3, null, null, 4, 5]
• Serialized: "1,2,N,N,3,4,N,N,5,N,N"

Why preorder with null markers? The null markers make the tree structure unambiguous. Without them, you’d need both preorder and inorder traversals to reconstruct the tree. With null markers, preorder alone is sufficient.

Level-order (BFS) serialization

from collections import deque

class TreeCodecBFS:
    """Serialize using level-order traversal."""

    def serialize(self, root: TreeNode) -> str:
        """BFS serialization. O(n) time and space."""
        if not root:
            return ""

        tokens = []
        queue = deque([root])

        while queue:
            node = queue.popleft()
            if node is None:
                tokens.append("N")
            else:
                tokens.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)

        return ','.join(tokens)

    def deserialize(self, data: str) -> TreeNode:
        """BFS deserialization. O(n) time and space."""
        if not data:
            return None

        tokens = data.split(',')
        root = TreeNode(int(tokens[0]))
        queue = deque([root])
        i = 1

        while queue and i < len(tokens):
            node = queue.popleft()

            # Left child
            if tokens[i] != "N":
                node.left = TreeNode(int(tokens[i]))
                queue.append(node.left)
            i += 1

            # Right child
            if i < len(tokens) and tokens[i] != "N":
                node.right = TreeNode(int(tokens[i]))
                queue.append(node.right)
            i += 1

        return root

6. Encode and decode TinyURL (LeetCode 535)

Design a URL shortening service. This is more of a system design problem, but the coding version tests your understanding of encoding:

import random
import string

class TinyURL:
    """Simple URL shortener with random code generation."""

    def __init__(self):
        self.url_to_code = {}
        self.code_to_url = {}
        self.chars = string.ascii_letters + string.digits
        self.base_url = "http://tinyurl.com/"

    def encode(self, long_url: str) -> str:
        """Generate a short URL. O(1) amortized."""
        if long_url in self.url_to_code:
            return self.base_url + self.url_to_code[long_url]

        # Generate random 6-character code
        while True:
            code = ''.join(random.choices(self.chars, k=6))
            if code not in self.code_to_url:
                break

        self.url_to_code[long_url] = code
        self.code_to_url[code] = long_url
        return self.base_url + code

    def decode(self, short_url: str) -> str:
        """Retrieve original URL. O(1)."""
        code = short_url.replace(self.base_url, "")
        return self.code_to_url.get(code, "")

Base62 encoding approach

For a deterministic mapping, use a counter with Base62 encoding:

class TinyURLBase62:
    """URL shortener using Base62 encoding of sequential IDs."""

    def __init__(self):
        self.id_to_url = {}
        self.url_to_id = {}
        self.counter = 0
        self.chars = string.ascii_lowercase + string.ascii_uppercase + string.digits

    def _id_to_base62(self, num: int) -> str:
        """Convert integer to Base62 string."""
        if num == 0:
            return self.chars[0]
        result = []
        while num > 0:
            result.append(self.chars[num % 62])
            num //= 62
        return ''.join(reversed(result))

    def encode(self, long_url: str) -> str:
        """Encode with sequential ID. O(1)."""
        if long_url in self.url_to_id:
            return "http://tinyurl.com/" + self._id_to_base62(self.url_to_id[long_url])

        self.counter += 1
        self.id_to_url[self.counter] = long_url
        self.url_to_id[long_url] = self.counter
        return "http://tinyurl.com/" + self._id_to_base62(self.counter)

    def decode(self, short_url: str) -> str:
        """Decode Base62 back to ID and look up URL. O(1)."""
        code = short_url.split("/")[-1]
        num = 0
        for c in code:
            num = num * 62 + self.chars.index(c)
        return self.id_to_url.get(num, "")

7. Count and say (LeetCode 38)

The “count and say” sequence describes the previous term:

• 1: “1”
• 2: “11” (one 1)
• 3: “21” (two 1s)
• 4: “1211” (one 2, one 1)

This is essentially iterative run-length encoding:

def count_and_say(n: int) -> str:
    """Generate the nth term of count-and-say. O(2^n) time worst case."""
    result = "1"

    for _ in range(n - 1):
        next_result = []
        i = 0
        while i < len(result):
            char = result[i]
            count = 0
            while i < len(result) and result[i] == char:
                i += 1
                count += 1
            next_result.append(str(count))
            next_result.append(char)
        result = ''.join(next_result)

    return result

Big-O summary

Problem	Time	Space
Encode/decode strings (length-prefix)	O(n)	O(n)
Run-length encode/decode	O(n)	O(n)
Decode string “3[a2[c]]“	O(n * max_k)	O(n)
String compression (in-place)	O(n)	O(1)
Serialize/deserialize tree	O(n)	O(n)
TinyURL encode/decode	O(1)	O(n) total
Count and say	O(2^n)	O(2^n)

Practice problems

1. Encode and Decode Strings (LeetCode 271) — Length-prefix protocol design
2. String Compression (LeetCode 443) — In-place two-pointer compression
3. Decode String (LeetCode 394) — Stack-based nested bracket decoding
4. Count and Say (LeetCode 38) — Iterative RLE
5. Serialize and Deserialize Binary Tree (LeetCode 297) — Preorder with null markers
6. Serialize and Deserialize BST (LeetCode 449) — Optimized for BST properties
7. Encode and Decode TinyURL (LeetCode 535) — Hashing and Base62
8. Decode Ways (LeetCode 91) — DP-based decoding (related concept)
9. Restore IP Addresses (LeetCode 93) — Backtracking-based decoding

Key takeaways

• Length-prefix is the most robust encoding scheme — it handles any content including the delimiter itself. Use length#content format.
• Run-length encoding is simple but only effective for data with long runs. Know the pattern for interview RLE problems.
• Stack is essential for decoding nested structures like "3[a2[c]]". Push state when entering a bracket, pop and combine when exiting.
• In-place compression uses the two-pointer technique — a read pointer scans ahead while a write pointer fills in the compressed output.
• Serialization of trees requires handling null nodes explicitly. Preorder with null markers is the cleanest approach and only needs one traversal.
• Base62 encoding converts integers to compact string representations — useful for URL shorteners and similar systems.