#6 Medium Time O(n) Space O(n) Animated

Encode and Decode Strings

Design an algorithm to encode and decode a list of strings.

LeetCode ↗

Tutor Mode Build the mental model before you memorize the code.

1 Predict
2 Trace
3 Explain
4 Implement

Pattern Hashing for constant-time memory

Trade one linear scan for a small lookup structure so each value is handled once.

Approach: Length Prefix (Chunking)

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Core Insight

Trade one linear scan for a small lookup structure so each value is handled once.

Common Pitfall

Do not overwrite information you still need before checking the current value.

Description

Design an algorithm to encode and decode a list of strings.

Constraints

Time Complexity: O(n)
Space Complexity: O(n)

Solution — Length Prefix (Chunking)

TimeO(n) SpaceO(n)

Implementation Plan

Translate the invariant into these small, testable moves.

Create the lookup structure.
Scan each value once.
Check the needed relationship before updating state.
Return as soon as the answer is determined.

class Codec:
    def encode(self, strs):
        res = ""
        for s in strs:
            res += str(len(s)) + "#" + s
        return res

    def decode(self, s):
        res = []
        i = 0
        while i < len(s):
            j = i
            while s[j] != "#":
                j += 1
            length = int(s[i:j])
            res.append(s[j + 1 : j + 1 + length])
            i = j + 1 + length
        return res

Top K Frequent Elements

Product of Array Except Self

Encode and Decode Strings

Steps

Description

Constraints

Tags

Solution — Length Prefix (Chunking)