Encode and Decode Strings (LeetCode 271)
You will see how writing each string's length in front of it lets a list of strings travel as one string, whatever characters they hold.
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"]dummy_input = [""][""]⚖️Formal Constraints & Bounds
1 <= strs.length <= 2000 <= strs[i].length <= 200strs[i]contains any possible characters out of256valid ASCII characters.
Why It Works & Core Invariant
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. |
Target: Encode and Decode Strings (LeetCode 271). The reader learns where `s` ends before it reads a single character of it, so `s` may hold anything.
Intervals sorted by start coordinate; monotonic stack preserves strictly increasing or decreasing element values.
Sweep: if curr.start <= prev.end: merge; Stack: while stack and nums[i] >= stack[-1]: stack.pop().
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.
🪄 The Mathematical Harmony / Magic Trick
parts.append(str(len(s)) + "#" + s)j = s.index("#", i)length = int(s[i:j])strs.append(s[j + 1 : j + 1 + length])i = j + 1 + length 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.
💡 Summary
Write str(len(s)) + "#" + s for every string; to decode, find the # that ends the digits, take exactly length characters and jump i = j + 1 + length, never looking inside the text. Every character is written once and copied once: time and space, for strings and characters.
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
You will see how a senior engineer spots a format that must carry any character and defends the length prefix out loud.
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
In decode, i always sits on the first digit of a length: 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 lands on the next length.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Count, never search:
["4#ab", "", "#"]encodes to"4#4#ab0#1##", and a decoder that reads each string up to the next#, or splits on#, cuts"4#ab"in two. Onlyi = j + 1 + lengthjumps safely over the text.Read every digit of the length,
int(s[i:j]), notint(s[i]): a string of 10 to 200 characters has a two- or three-digit length.An empty string is a piece too:
[""]encodes to"0#"and decodes to[""]. Skipping empty strings inencodereturns[].Start the search at
i,s.index("#", i): withouti, it finds the first#of the whole message every time.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use 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. Counting never looks inside the text. 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.
So: the size goes before the data, and decode counts length characters instead of searching the text.
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)
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).
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.
Never look inside the text: splitting on # or reading up to the next # breaks on "4#ab". 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, a length that lies is a buffer over-read; Python's slice just returns fewer characters.
Core Algorithmic State Invariants
`encode` writes `str(len(s)) + "#" + s`, so the reader knows where each string ends before it reads any of it, and a string may hold any character.
`decode` only searches for the `#` that ends a length (`s.index("#", i)`), then takes exactly `length` characters and jumps `i = j + 1 + length`: a `#` or a digit inside the text is never read as format.
`encode` writes each character once and `decode` copies it once; the search for `#` reads at most four characters per string. That is O(N + L) time and space for N strings of L characters in total.
Encode and Decode Strings (LeetCode 271)
You will see how writing each string's length in front of it lets a list of strings travel as one string, whatever characters they hold.
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"]dummy_input = [""][""]⚖️Formal Constraints & Bounds
1 <= strs.length <= 2000 <= strs[i].length <= 200strs[i]contains any possible characters out of256valid ASCII characters.
Why It Works & Core Invariant
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. |
Target: Encode and Decode Strings (LeetCode 271). The reader learns where `s` ends before it reads a single character of it, so `s` may hold anything.
Intervals sorted by start coordinate; monotonic stack preserves strictly increasing or decreasing element values.
Sweep: if curr.start <= prev.end: merge; Stack: while stack and nums[i] >= stack[-1]: stack.pop().
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.
🪄 The Mathematical Harmony / Magic Trick
parts.append(str(len(s)) + "#" + s)j = s.index("#", i)length = int(s[i:j])strs.append(s[j + 1 : j + 1 + length])i = j + 1 + length 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.
💡 Summary
Write str(len(s)) + "#" + s for every string; to decode, find the # that ends the digits, take exactly length characters and jump i = j + 1 + length, never looking inside the text. Every character is written once and copied once: time and space, for strings and characters.
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
You will see how a senior engineer spots a format that must carry any character and defends the length prefix out loud.
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
In decode, i always sits on the first digit of a length: 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 lands on the next length.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Count, never search:
["4#ab", "", "#"]encodes to"4#4#ab0#1##", and a decoder that reads each string up to the next#, or splits on#, cuts"4#ab"in two. Onlyi = j + 1 + lengthjumps safely over the text.Read every digit of the length,
int(s[i:j]), notint(s[i]): a string of 10 to 200 characters has a two- or three-digit length.An empty string is a piece too:
[""]encodes to"0#"and decodes to[""]. Skipping empty strings inencodereturns[].Start the search at
i,s.index("#", i): withouti, it finds the first#of the whole message every time.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use 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. Counting never looks inside the text. 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.
So: the size goes before the data, and decode counts length characters instead of searching the text.
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)
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).
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.
Never look inside the text: splitting on # or reading up to the next # breaks on "4#ab". 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, a length that lies is a buffer over-read; Python's slice just returns fewer characters.
Core Algorithmic State Invariants
`encode` writes `str(len(s)) + "#" + s`, so the reader knows where each string ends before it reads any of it, and a string may hold any character.
`decode` only searches for the `#` that ends a length (`s.index("#", i)`), then takes exactly `length` characters and jumps `i = j + 1 + length`: a `#` or a digit inside the text is never read as format.
`encode` writes each character once and `decode` copies it once; the search for `#` reads at most four characters per string. That is O(N + L) time and space for N strings of L characters in total.
| Canonical Invariant | Concrete Code | Engineering Rationale |
|---|---|---|
| One piece per string, the size in front | parts.append(str(len(s)) + "#" + s) | The reader learns where `s` ends before it reads a single character of it, so `s` may hold anything. |
| Join the pieces once | return "".join(parts) | One pass over all the characters, instead of copying a growing string for every piece. |
| A read position that always sits on a size | i = 0 | Every piece starts with its length, so `i` is on a length at the start and after every jump. |
| Find the end of the size, and only that | j = s.index("#", i) | The search starts at `i` and stops at the first `#`: the digits of a length never hold one, so this `#` is the separator. |
| Read every digit of the size | length = int(s[i:j]) | A length can be 0 or up to 200, so it may have one, two or three digits. |
| Take exactly that many characters | strs.append(s[j + 1 : j + 1 + length]) | The trap: count, never search. A `#` or a digit inside the text is just part of the text. |
| Jump to the next size | i = j + 1 + length | The text is skipped without being read, so the loop runs once per string. |