Encode and Decode Strings (LeetCode 271)
Two programs have to hand a list of strings to each other, but the channel between them carries a single string and nothing else. Build the class Codec that makes this possible:
encode(strs)takes the list of stringsstrsand returns one string that stands for all of them.decode(s)takes a string made byencodeand returns the original list: the same strings in the same order, empty strings included.
The two methods run on different machines. A new Codec decodes what another Codec encoded, so the encoded string has to carry everything, and nothing can be kept in the object between the two calls. The strings may contain any of the 256 ASCII characters, so any separator you might pick can also appear inside a string. The judge runs your code twice, as two separate programs, so nothing stored in a class or a global variable survives either. As in an interview, design the format yourself instead of reaching for library serialization (for example eval or json); the judge itself only checks that the list comes back. It also has machine 1 encode a second, different list right after yours, so a list kept from the last call can't come back.
The judge passes one list, dummy_input, encodes it, decodes the result on a new Codec, and expects the same list back.
Follow-up: can your format work for any set of characters, not only these 256?
Worked Examples
dummy_input = ["Hello","World"]["Hello","World"]encode turns the two strings into one, for example "5#Hello5#World", and a new Codec decodes that string back into ["Hello","World"].dummy_input = [""][""]"0#".⚖️Formal Constraints & Bounds
1 <= strs.length <= 2000 <= strs[i].length <= 200strs[i]contains any possible characters out of256valid ASCII characters.
Core Insight
A separator alone can never work, because any character may appear inside a string. Write each string's length in front of it instead: the reader reads the digits up to the first #, then takes exactly that many characters, whatever they are.
Real-World Scenario & Production Applications
Any protocol that packs several values into one message has this problem. Redis's wire protocol sends a string as $, its length, a line break, then the bytes, and HTTP/1.1 chunked transfer puts each chunk's size before its data. With the size in front, the reader never has to guess where a value ends, whatever bytes the value holds.
Step-by-Step Execution Trace Table
The debugger's first preset, the trap case strs = ["4#ab", "", "#"]: encode returns "4#4#ab0#1##" (11 characters). decode then reads:
i | j = s.index("#", i) | length = int(s[i:j]) | s[j + 1 : j + 1 + length] | strs after | next i |
|---|---|---|---|---|---|
| 0 | 1 | 4 | "4#ab": it holds a #, but the code counts 4 characters and never looks inside | ["4#ab"] | 6 |
| 6 | 7 | 0 | "": an empty string is still a piece | ["4#ab", ""] | 8 |
| 8 | 9 | 1 | "#" | ["4#ab", "", "#"] | 11 |
| 11 | i < len(s) is false: the loop ends | ["4#ab", "", "#"] |
| 1 | Any character may appear inside a string, so no separator is safe on its own: tell the reader where each string ends before it reads the string, by writing its length in front. |
| 2 | Keep this true in `decode`: `i` always sits on the first digit of a length. The first `#` from `i` ends the length, because digits never contain a `#`. |
| 3 | The shape: `encode` builds one piece per string and joins the pieces once; `decode` is one `while` loop over the message, and each round reads one length, then one string, then moves the read position past that string. |
| 4 | The trap: jump with `i = j + 1 + length` and never search the text for the next `#`. `["4#ab", "", "#"]` encodes to `"4#4#ab0#1##"`, and a split on `#` cuts `"4#ab"` apart. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Joining the strings with a separator looks like the obvious move, but the strings may contain any character, so whatever separator you pick can appear inside a string, and the reader can't tell a real separator from a copy. Length-Prefix Encoding tells the reader where each string ends before it reads the string: encode writes str(len(s)), then a #, then s itself. The only # the reader ever searches for is the one right after the digits, and digits never contain a #. After that it counts: it takes exactly length characters and jumps past them, so a # or a digit inside the text is never read as part of the format.
📦 The Analogy: Labeled Parcels on a Conveyor Belt
Parcels of different sizes travel on one belt, touching each other, with no gaps between them. Looking for the gap between two parcels doesn't work, since a parcel may itself be made of pieces that look like several parcels. So every parcel carries a label on its front edge: "the next 4 boxes are me". The worker at the other end reads the label, counts off 4 boxes without opening any of them, and the next thing on the belt is the next label. An empty parcel is just a label that says 0.
🔑 Why It Works
i always sits on the first digit of a length. The first # from i must end that length, because the digits str(len(s)) writes never include a #. From there the code only counts: the text is the next length characters, and i = j + 1 + length lands on the next length. The trap is to read the text by looking for the next #, or to split the whole message on #: a string like "4#ab" holds a # and something that looks like a length, and only counting gets past it safely.
Searching inside the text (the trap):
["4#ab", "", "#"]encodes to"4#4#ab0#1##". Splitting on#, or reading each string up to the next#, cuts"4#ab"in two; take exactlylengthcharacters withs[j + 1 : j + 1 + length]and jumpi = j + 1 + length.A separator alone:
"#".join(strs)looks fine until a string contains#. Any character may appear, so no separator is safe without a length (or an escape scheme) in front.Reading one digit of the length:
int(s[i])breaks as soon as a string has 10 or more characters. Read up to the#:int(s[i:j]).Dropping empty strings: a length of
0is still a piece,"0#". Skip it and[""]comes back as[].Searching from the start:
s.index("#")withoutifinds the first#of the whole message every time. Pass the start:s.index("#", i).Keeping the list around: saving
strson the object, on the class or in a global variable inencodeand returning it fromdecodefails: the judge decodes in a second, separate run of your code, where only the encoded string arrives.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
The strings "may contain any of the 256 ASCII characters", and "a new Codec decodes what another Codec encoded": no separator can be kept out of the strings, and the encoded string has to carry everything the reader needs. That is the signal for Length-Prefix Encoding: write each string's size before the string.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Decision rule in decode: j = s.index("#", i) ends the digits, length = int(s[i:j]), the string is s[j + 1 : j + 1 + length], and i = j + 1 + length moves to the next length.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Count, never search: jump with
i = j + 1 + length(the card's first gotcha shows an input that breaks a search, and the debugger's trap preset runs it).
The 60-Second Interview Pitch
Say this out loud before you type a single line
This is Encode and Decode Strings, solved with length-prefix encoding. The strings can contain any character, so no separator is safe on its own: whatever I pick could be inside a string. So I write each string's length, then a hash sign, then the string itself. To decode, I keep an index i that always points at the start of a length. I find the first hash sign from i, which ends the length because digits never contain one, parse every digit, then take exactly that many characters, whatever they are, and jump i past them. The trap is reading the text by looking for the next hash sign, or splitting on it: a string like 4, hash, a, b would be cut in two. An empty string still gets its piece, zero and a hash sign. Each character is written once and copied once, so it's O(N plus L) time and space, for N strings and L characters.
Complexity & Mathematical Proof
O(N + L)
Look at the code. encode runs its loop once per string: str(len(s)) has at most three digits and building the piece copies s, so the loop costs O(N + L), and "".join(parts) copies every piece once more, O(N + L). In decode, every round of the while loop reads one piece: s.index("#", i) starts on the first digit of a length and stops at most four characters later, int(s[i:j]) parses at most three digits, and the slice copies length characters. There is one round per string, so the loop costs O(N + L). Total: O(N + L).
O(N + L)
The encoded string holds the L characters plus at most four characters of framing per string, O(N + L); parts holds the same pieces before the join. decode returns the N strings, O(N + L), and keeps only i, j and length besides.
T(N, L) = O(N + L) to encode + O(N + L) to decode = O(N + L)
Derivation Progression
O(N + L)
One piece per string: at most three digits, one #, and a copy of s.
O(N + L)
"".join(parts) copies every piece once into the encoded string.
N · O(1) + O(L)
One round per string: s.index("#", i) reads at most four characters and int(s[i:j]) at most three digits; the slices copy L characters in all.
O(N + L)
Each character is written once and copied once, plus a constant amount of framing per string.
Variable Definitions
Number of strings, len(strs) (at most 200)
Total number of characters in all the strings
Memory Architecture & Bounds
O(1) Iterative, no recursion
O(N + L): parts in encode (the pieces before the join)
O(N + L): the encoded string, and the decoded list
Boundary Best / Worst Cases
: every character must be written and read
: the same work whatever the characters are
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "any of the 256 ASCII characters", "nothing can be kept in the object between the two calls". Every character may appear inside a string, so no separator is safe, and the encoded string must carry everything: Length-Prefix Encoding, the size before the data.
strings of up to characters: at most characters of text, plus at most four characters of framing per string. Any linear format is instant at this size, so the risk is correctness, not speed.
Binary protocols use a fixed-width length (for example 4 bytes) instead of digits and a separator, so the reader can size its buffer before the data arrives. A reader of untrusted input must also check that j + 1 + length stays inside the message: in C, trusting a length field that is larger than the bytes left in the message causes a buffer over-read; Python's slice just returns fewer characters.
Core Algorithmic State Invariants
- Why the
"#"Is Needed at All
Lengths have a varying number of digits, so without an end mark "12ab" could be a length of 12, or a length of 1 followed by text starting with 2. The "#" only ends the digits; it never has to be kept out of the text.
- Escaping Is the Other Fix
The other classic way to use a separator is to escape it inside the text (for example, double every "#"). It works, but decode must then read every character to undo the escapes, while the length prefix lets it jump over the text.
Encode and Decode Strings (LeetCode 271)
Two programs have to hand a list of strings to each other, but the channel between them carries a single string and nothing else. Build the class Codec that makes this possible:
encode(strs)takes the list of stringsstrsand returns one string that stands for all of them.decode(s)takes a string made byencodeand returns the original list: the same strings in the same order, empty strings included.
The two methods run on different machines. A new Codec decodes what another Codec encoded, so the encoded string has to carry everything, and nothing can be kept in the object between the two calls. The strings may contain any of the 256 ASCII characters, so any separator you might pick can also appear inside a string. The judge runs your code twice, as two separate programs, so nothing stored in a class or a global variable survives either. As in an interview, design the format yourself instead of reaching for library serialization (for example eval or json); the judge itself only checks that the list comes back. It also has machine 1 encode a second, different list right after yours, so a list kept from the last call can't come back.
The judge passes one list, dummy_input, encodes it, decodes the result on a new Codec, and expects the same list back.
Follow-up: can your format work for any set of characters, not only these 256?
Worked Examples
dummy_input = ["Hello","World"]["Hello","World"]encode turns the two strings into one, for example "5#Hello5#World", and a new Codec decodes that string back into ["Hello","World"].dummy_input = [""][""]"0#".⚖️Formal Constraints & Bounds
1 <= strs.length <= 2000 <= strs[i].length <= 200strs[i]contains any possible characters out of256valid ASCII characters.
Core Insight
A separator alone can never work, because any character may appear inside a string. Write each string's length in front of it instead: the reader reads the digits up to the first #, then takes exactly that many characters, whatever they are.
Real-World Scenario & Production Applications
Any protocol that packs several values into one message has this problem. Redis's wire protocol sends a string as $, its length, a line break, then the bytes, and HTTP/1.1 chunked transfer puts each chunk's size before its data. With the size in front, the reader never has to guess where a value ends, whatever bytes the value holds.
Step-by-Step Execution Trace Table
The debugger's first preset, the trap case strs = ["4#ab", "", "#"]: encode returns "4#4#ab0#1##" (11 characters). decode then reads:
i | j = s.index("#", i) | length = int(s[i:j]) | s[j + 1 : j + 1 + length] | strs after | next i |
|---|---|---|---|---|---|
| 0 | 1 | 4 | "4#ab": it holds a #, but the code counts 4 characters and never looks inside | ["4#ab"] | 6 |
| 6 | 7 | 0 | "": an empty string is still a piece | ["4#ab", ""] | 8 |
| 8 | 9 | 1 | "#" | ["4#ab", "", "#"] | 11 |
| 11 | i < len(s) is false: the loop ends | ["4#ab", "", "#"] |
| 1 | Any character may appear inside a string, so no separator is safe on its own: tell the reader where each string ends before it reads the string, by writing its length in front. |
| 2 | Keep this true in `decode`: `i` always sits on the first digit of a length. The first `#` from `i` ends the length, because digits never contain a `#`. |
| 3 | The shape: `encode` builds one piece per string and joins the pieces once; `decode` is one `while` loop over the message, and each round reads one length, then one string, then moves the read position past that string. |
| 4 | The trap: jump with `i = j + 1 + length` and never search the text for the next `#`. `["4#ab", "", "#"]` encodes to `"4#4#ab0#1##"`, and a split on `#` cuts `"4#ab"` apart. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Joining the strings with a separator looks like the obvious move, but the strings may contain any character, so whatever separator you pick can appear inside a string, and the reader can't tell a real separator from a copy. Length-Prefix Encoding tells the reader where each string ends before it reads the string: encode writes str(len(s)), then a #, then s itself. The only # the reader ever searches for is the one right after the digits, and digits never contain a #. After that it counts: it takes exactly length characters and jumps past them, so a # or a digit inside the text is never read as part of the format.
📦 The Analogy: Labeled Parcels on a Conveyor Belt
Parcels of different sizes travel on one belt, touching each other, with no gaps between them. Looking for the gap between two parcels doesn't work, since a parcel may itself be made of pieces that look like several parcels. So every parcel carries a label on its front edge: "the next 4 boxes are me". The worker at the other end reads the label, counts off 4 boxes without opening any of them, and the next thing on the belt is the next label. An empty parcel is just a label that says 0.
🔑 Why It Works
i always sits on the first digit of a length. The first # from i must end that length, because the digits str(len(s)) writes never include a #. From there the code only counts: the text is the next length characters, and i = j + 1 + length lands on the next length. The trap is to read the text by looking for the next #, or to split the whole message on #: a string like "4#ab" holds a # and something that looks like a length, and only counting gets past it safely.
Searching inside the text (the trap):
["4#ab", "", "#"]encodes to"4#4#ab0#1##". Splitting on#, or reading each string up to the next#, cuts"4#ab"in two; take exactlylengthcharacters withs[j + 1 : j + 1 + length]and jumpi = j + 1 + length.A separator alone:
"#".join(strs)looks fine until a string contains#. Any character may appear, so no separator is safe without a length (or an escape scheme) in front.Reading one digit of the length:
int(s[i])breaks as soon as a string has 10 or more characters. Read up to the#:int(s[i:j]).Dropping empty strings: a length of
0is still a piece,"0#". Skip it and[""]comes back as[].Searching from the start:
s.index("#")withoutifinds the first#of the whole message every time. Pass the start:s.index("#", i).Keeping the list around: saving
strson the object, on the class or in a global variable inencodeand returning it fromdecodefails: the judge decodes in a second, separate run of your code, where only the encoded string arrives.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
The strings "may contain any of the 256 ASCII characters", and "a new Codec decodes what another Codec encoded": no separator can be kept out of the strings, and the encoded string has to carry everything the reader needs. That is the signal for Length-Prefix Encoding: write each string's size before the string.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Decision rule in decode: j = s.index("#", i) ends the digits, length = int(s[i:j]), the string is s[j + 1 : j + 1 + length], and i = j + 1 + length moves to the next length.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Count, never search: jump with
i = j + 1 + length(the card's first gotcha shows an input that breaks a search, and the debugger's trap preset runs it).
The 60-Second Interview Pitch
Say this out loud before you type a single line
This is Encode and Decode Strings, solved with length-prefix encoding. The strings can contain any character, so no separator is safe on its own: whatever I pick could be inside a string. So I write each string's length, then a hash sign, then the string itself. To decode, I keep an index i that always points at the start of a length. I find the first hash sign from i, which ends the length because digits never contain one, parse every digit, then take exactly that many characters, whatever they are, and jump i past them. The trap is reading the text by looking for the next hash sign, or splitting on it: a string like 4, hash, a, b would be cut in two. An empty string still gets its piece, zero and a hash sign. Each character is written once and copied once, so it's O(N plus L) time and space, for N strings and L characters.
Complexity & Mathematical Proof
O(N + L)
Look at the code. encode runs its loop once per string: str(len(s)) has at most three digits and building the piece copies s, so the loop costs O(N + L), and "".join(parts) copies every piece once more, O(N + L). In decode, every round of the while loop reads one piece: s.index("#", i) starts on the first digit of a length and stops at most four characters later, int(s[i:j]) parses at most three digits, and the slice copies length characters. There is one round per string, so the loop costs O(N + L). Total: O(N + L).
O(N + L)
The encoded string holds the L characters plus at most four characters of framing per string, O(N + L); parts holds the same pieces before the join. decode returns the N strings, O(N + L), and keeps only i, j and length besides.
T(N, L) = O(N + L) to encode + O(N + L) to decode = O(N + L)
Derivation Progression
O(N + L)
One piece per string: at most three digits, one #, and a copy of s.
O(N + L)
"".join(parts) copies every piece once into the encoded string.
N · O(1) + O(L)
One round per string: s.index("#", i) reads at most four characters and int(s[i:j]) at most three digits; the slices copy L characters in all.
O(N + L)
Each character is written once and copied once, plus a constant amount of framing per string.
Variable Definitions
Number of strings, len(strs) (at most 200)
Total number of characters in all the strings
Memory Architecture & Bounds
O(1) Iterative, no recursion
O(N + L): parts in encode (the pieces before the join)
O(N + L): the encoded string, and the decoded list
Boundary Best / Worst Cases
: every character must be written and read
: the same work whatever the characters are
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "any of the 256 ASCII characters", "nothing can be kept in the object between the two calls". Every character may appear inside a string, so no separator is safe, and the encoded string must carry everything: Length-Prefix Encoding, the size before the data.
strings of up to characters: at most characters of text, plus at most four characters of framing per string. Any linear format is instant at this size, so the risk is correctness, not speed.
Binary protocols use a fixed-width length (for example 4 bytes) instead of digits and a separator, so the reader can size its buffer before the data arrives. A reader of untrusted input must also check that j + 1 + length stays inside the message: in C, trusting a length field that is larger than the bytes left in the message causes a buffer over-read; Python's slice just returns fewer characters.
Core Algorithmic State Invariants
- Why the
"#"Is Needed at All
Lengths have a varying number of digits, so without an end mark "12ab" could be a length of 12, or a length of 1 followed by text starting with 2. The "#" only ends the digits; it never has to be kept out of the text.
- Escaping Is the Other Fix
The other classic way to use a separator is to escape it inside the text (for example, double every "#"). It works, but decode must then read every character to undo the escapes, while the length prefix lets it jump over the text.