Builds on Digit Manipulation, which you haven’t finished yet.
Length-Prefix Encoding
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?
encode turns the two strings into one, for example "5#Hello5#World", and a new Codec decodes that string back into ["Hello","World"].Encode and Decode Strings
| 1 | class Codec: |
| 2 | """Encode and Decode Strings: write each string's length and a "#" in front of it. |
| 3 | Time: O(N + L) | Space: O(N + L) |
| 4 | """ |
| 5 | Â |
| 6 | def encode(self, strs: list[str]) -> str: |
| 7 | parts: list[str] = [] # One size-prefixed piece per string |
| 8 | for s in strs: |
| 9 | # 1. Write Each String's Size Before Its Data: |
| 10 | # Any character may appear inside a string, so no separator is safe; the reader learns where |
| 11 | # a piece ends before it reads a single character of it. |
| 12 | parts.append(str(len(s)) + "#" + s) |
| 13 | return "".join(parts) |
| 14 | Â |
| 15 | def decode(self, s: str) -> list[str]: |
| 16 | strs: list[str] = [] |
| 17 | i = 0 # Always the first digit of a length |
| 18 | while i < len(s): |
| 19 | # 1. Find Where The Size Ends: |
| 20 | # The first "#" from i must end the length, because digits written by encode never contain a "#". |
| 21 | j = s.index("#", i) |
| 22 | length = int(s[i:j]) |
| 23 | Â |
| 24 | # 2. Take Exactly That Many Characters And Jump Past Them: |
| 25 | # Counting instead of searching means a "#" or a digit inside the text is never read as part |
| 26 | # of the format. |
| 27 | strs.append(s[j + 1 : j + 1 + length]) |
| 28 | i = j + 1 + length |
| 29 | return strs |
str(len(s)), a "#", then exactly len(s) characters, so in decode the index i always sits on the first digit of a length.Any character can appear inside a string, so no separator can mark where one ends: write the size before the data instead, str(len(s)) + "#" + s in encode. Digits never contain a "#", so in decode the first "#" from i, j = s.index("#", i), is exactly where the length ends, and the length says where the text ends: take s[j + 1 : j + 1 + length] and jump i = j + 1 + length without reading the text, so the next piece starts on a length again. The trap is reading the text by searching for the next "#" or splitting the message on "#": the strings may hold "#" and digits themselves, as in ["4#ab", "", "#"], and only counting length characters gets past them safely.
See it run
Encode and Decode Strings, step by step
message ""i -
The top row is the message. The bottom row is the list of strings: the input of encode first, then the result of decode, filled from column 0. Two quote marks mean an empty string.
writea character that encode just wrote into the messagestringthe string in the list strs that is being written or has just been readithe index where the next length startssizea digit of the length that decode readsjthe first # after i, which ends the lengthtexta character that decode takes as part of the string#/digita # or a digit inside the string, which decode takes as text
Start: encode gets strs = ["4#ab", "", "#"]. It writes each string as its length, a "#", then the string.
Gotcha 1 of 4
- The trap
Gotcha 1: Splitting the message on
"#"Mistakedef encode(self, strs): return "#".join(strs) def decode(self, s): return s.split("#")Fixstrs.append(s[j + 1 : j + 1 + length]) i = j + 1 + lengthWhat happens: Any character can appear inside a string,
"#"included. A split on"#"cuts such a string into pieces. Reading up to the next"#"cuts it in the same way.decodemust take exactlylengthcharacters and jump over them withi = j + 1 + length.Example: strs = ["4#ab", "", "#"]Mistake: returns ['4', 'ab', '', '', '']Fix: returns ['4#ab', '', '#']
- A tree's shape must survive, not just a list of strings, as in Construct Binary Tree from Preorder and Inorder Traversal (LC 105): the reader rebuilds which value is whose child from two traversal orders, so no length prefix helps. See Construct Binary Tree
- The format is given and nests repeat counts in brackets, as in Decode String (LC 394): you parse someone else's encoding, opened and closed by
[and], instead of designing one. See Nesting Stack
Deep Dive
Why no separator is safe, and why a length is
In Encode and Decode Strings (LC 271), each string can hold any character. A separator character such as "#" can then appear inside a string, and decode cannot tell it from the real separator.
Example: join ["4#ab", "", "#"] with "#" and split the result. The joined text is "4#ab###". The split gives ["4", "ab", "", "", ""], which has five strings and not three.
The fix is to write the size of each string before the string. encode writes str(len(s)) + "#" + s. The reader learns where a piece ends before it reads any character of the piece, so the content of the piece cannot confuse it.
For the same list, the message is "4#4#ab0#1##". The pieces are 4#4#ab, 0# and 1##.
One trace: encode, then decode a string that holds # and digits
The board first runs encode on ["4#ab", "", "#"]. It writes the three pieces into the message. Then decode reads only the message.
In decode, i is on the first digit of a length. j = s.index("#", i) finds the first "#" from i, and int(s[i:j]) is the length. For the first piece, i = 0, j = 1 and length = 4.
Then s[j + 1 : j + 1 + length] takes exactly 4 characters, which are "4#ab". The text holds a digit and a "#", and neither is read as format. This step is marked as the trap on the board. The loop sets i = 6 and does not read the text again.
The second piece has length 0, so it takes no characters and returns "". The third piece has length 1 and takes the single character "#". The loop ends at i = 11, the end of the message.
Why i is always on the first digit of a length
This is the invariant of decode. It holds at the start, because i = 0 and the message starts with a length. It holds after each piece, because i = j + 1 + length is the first character after the text, and encode wrote the next length there.
The first "#" from i ends the length, because the digits that encode writes never contain "#". This is why s.index("#", i) is safe. The "#" inside the text of a string is always after j, and the loop never searches there.
Pass i to s.index. Without i, the search starts at the beginning again, finds the first "#", and s[i:j] is empty for the second string. Then int("") raises a ValueError.
Read all the digits with int(s[i:j]). A string of 10 or more characters has a length with two or more digits. int(s[i]) reads only the first digit and takes too few characters.
Do not skip an empty string in encode. It is written as "0#". Skipping it makes decode return a shorter list.
The cost, and where the same idea is used
Let N be the number of strings and L the total number of characters. encode writes N prefixes and copies L characters, so it is O(N + L). decode reads each prefix once, and each slice copies the characters of one string, so it is also O(N + L). The message holds O(N + L) characters, so the space is O(N + L).
decode never scans the text of a string to find its end. It jumps over the text with i = j + 1 + length. That is why the text can hold any character.
The same idea is used in network formats. The Content-Length header of HTTP/1.1 states the size of the body before the body, so the receiver knows where the message ends.
The separator is a choice. Any character that is not a digit would work in place of "#". The important rule is that the length ends at a character that digits cannot contain.
60-Second Pitch
"The strings can hold any character, so no separator is safe. I write the size before the data: str(len(s)) + "#" + s. In decode, i is always on the first digit of a length. The first "#" from i ends the length, because digits never contain it. Then I take exactly length characters and jump i past them without reading them. So a "#" or a digit inside a string is never read as format. Empty strings work too, as "0#". The time and the space are O(N + L)."
Common Questions
- Why not join the strings with a separator?
A string can hold any character, so it can hold the separator too.
decodecannot tell a separator inside a string from a real one. For["4#ab", "", "#"], a split on"#"gives five strings.- Why does the length come before the text?
The reader must know where a piece ends before it reads the piece. With the length first,
decodecounts characters and never searches the text for an end marker.- Why is the first
"#"fromialways the end of the length? The length is written with digits, and a digit is never
"#".iis on the first digit of a length, so the first"#"fromiis the one thatencodewrote after the length.- How are empty strings handled?
encodewrites"0#"for an empty string.decodereads the length 0, takes no characters and appends"". Skipping empty strings inencodewould lose them.- What are the time and space complexity?
O(N + L) time and O(N + L) space, where
Nis the number of strings andLis the total number of characters. Each prefix and each character is handled a constant number of times.
SWE Reasoning
Spot it
- A list of strings must travel as one string and come back exactly.
- The strings may hold any character, so no separator can be kept out of them.
- Empty strings are allowed and must come back.
- The format is read from left to right, and each piece must say how long it is.
decodereceives only the encoded message, so it cannot use anything else thatencodeknew.
The invariant, step by step
encodewritesstr(len(s)) + "#" + sfor each string and joins the pieces.decodestarts withi = 0, which is the first digit of the first length.j = s.index("#", i)is the end of the length, because digits never contain"#".length = int(s[i:j])is the size of the text.s[j + 1 : j + 1 + length]is exactly the text.i = j + 1 + lengthmoves to the next length. The text is never read for format, so a"#"or a digit inside it is safe.- The loop ends when
ireacheslen(s), andstrsholds the original list.
Traps
- Joining with a separator.
["4#ab", "", "#"]is split into five strings. - Searching for the next
"#"to find the end of the text. A"#"inside the text ends it too early. - Skipping empty strings. An empty string must be written as
"0#". s.index("#")withouti. The search finds the first"#"again andint("")raises aValueError.int(s[i])for the length. A length of 10 or more has several digits.
Practice
Builds on Digit Manipulation, which you haven’t finished yet.
Length-Prefix Encoding
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?
encode turns the two strings into one, for example "5#Hello5#World", and a new Codec decodes that string back into ["Hello","World"].Encode and Decode Strings
| 1 | class Codec: |
| 2 | """Encode and Decode Strings: write each string's length and a "#" in front of it. |
| 3 | Time: O(N + L) | Space: O(N + L) |
| 4 | """ |
| 5 | Â |
| 6 | def encode(self, strs: list[str]) -> str: |
| 7 | parts: list[str] = [] # One size-prefixed piece per string |
| 8 | for s in strs: |
| 9 | # 1. Write Each String's Size Before Its Data: |
| 10 | # Any character may appear inside a string, so no separator is safe; the reader learns where |
| 11 | # a piece ends before it reads a single character of it. |
| 12 | parts.append(str(len(s)) + "#" + s) |
| 13 | return "".join(parts) |
| 14 | Â |
| 15 | def decode(self, s: str) -> list[str]: |
| 16 | strs: list[str] = [] |
| 17 | i = 0 # Always the first digit of a length |
| 18 | while i < len(s): |
| 19 | # 1. Find Where The Size Ends: |
| 20 | # The first "#" from i must end the length, because digits written by encode never contain a "#". |
| 21 | j = s.index("#", i) |
| 22 | length = int(s[i:j]) |
| 23 | Â |
| 24 | # 2. Take Exactly That Many Characters And Jump Past Them: |
| 25 | # Counting instead of searching means a "#" or a digit inside the text is never read as part |
| 26 | # of the format. |
| 27 | strs.append(s[j + 1 : j + 1 + length]) |
| 28 | i = j + 1 + length |
| 29 | return strs |
str(len(s)), a "#", then exactly len(s) characters, so in decode the index i always sits on the first digit of a length.Any character can appear inside a string, so no separator can mark where one ends: write the size before the data instead, str(len(s)) + "#" + s in encode. Digits never contain a "#", so in decode the first "#" from i, j = s.index("#", i), is exactly where the length ends, and the length says where the text ends: take s[j + 1 : j + 1 + length] and jump i = j + 1 + length without reading the text, so the next piece starts on a length again. The trap is reading the text by searching for the next "#" or splitting the message on "#": the strings may hold "#" and digits themselves, as in ["4#ab", "", "#"], and only counting length characters gets past them safely.
See it run
Encode and Decode Strings, step by step
message ""i -
The top row is the message. The bottom row is the list of strings: the input of encode first, then the result of decode, filled from column 0. Two quote marks mean an empty string.
writea character that encode just wrote into the messagestringthe string in the list strs that is being written or has just been readithe index where the next length startssizea digit of the length that decode readsjthe first # after i, which ends the lengthtexta character that decode takes as part of the string#/digita # or a digit inside the string, which decode takes as text
Start: encode gets strs = ["4#ab", "", "#"]. It writes each string as its length, a "#", then the string.
Gotcha 1 of 4
- The trap
Gotcha 1: Splitting the message on
"#"Mistakedef encode(self, strs): return "#".join(strs) def decode(self, s): return s.split("#")Fixstrs.append(s[j + 1 : j + 1 + length]) i = j + 1 + lengthWhat happens: Any character can appear inside a string,
"#"included. A split on"#"cuts such a string into pieces. Reading up to the next"#"cuts it in the same way.decodemust take exactlylengthcharacters and jump over them withi = j + 1 + length.Example: strs = ["4#ab", "", "#"]Mistake: returns ['4', 'ab', '', '', '']Fix: returns ['4#ab', '', '#']
- A tree's shape must survive, not just a list of strings, as in Construct Binary Tree from Preorder and Inorder Traversal (LC 105): the reader rebuilds which value is whose child from two traversal orders, so no length prefix helps. See Construct Binary Tree
- The format is given and nests repeat counts in brackets, as in Decode String (LC 394): you parse someone else's encoding, opened and closed by
[and], instead of designing one. See Nesting Stack
Deep Dive
Why no separator is safe, and why a length is
In Encode and Decode Strings (LC 271), each string can hold any character. A separator character such as "#" can then appear inside a string, and decode cannot tell it from the real separator.
Example: join ["4#ab", "", "#"] with "#" and split the result. The joined text is "4#ab###". The split gives ["4", "ab", "", "", ""], which has five strings and not three.
The fix is to write the size of each string before the string. encode writes str(len(s)) + "#" + s. The reader learns where a piece ends before it reads any character of the piece, so the content of the piece cannot confuse it.
For the same list, the message is "4#4#ab0#1##". The pieces are 4#4#ab, 0# and 1##.
One trace: encode, then decode a string that holds # and digits
The board first runs encode on ["4#ab", "", "#"]. It writes the three pieces into the message. Then decode reads only the message.
In decode, i is on the first digit of a length. j = s.index("#", i) finds the first "#" from i, and int(s[i:j]) is the length. For the first piece, i = 0, j = 1 and length = 4.
Then s[j + 1 : j + 1 + length] takes exactly 4 characters, which are "4#ab". The text holds a digit and a "#", and neither is read as format. This step is marked as the trap on the board. The loop sets i = 6 and does not read the text again.
The second piece has length 0, so it takes no characters and returns "". The third piece has length 1 and takes the single character "#". The loop ends at i = 11, the end of the message.
Why i is always on the first digit of a length
This is the invariant of decode. It holds at the start, because i = 0 and the message starts with a length. It holds after each piece, because i = j + 1 + length is the first character after the text, and encode wrote the next length there.
The first "#" from i ends the length, because the digits that encode writes never contain "#". This is why s.index("#", i) is safe. The "#" inside the text of a string is always after j, and the loop never searches there.
Pass i to s.index. Without i, the search starts at the beginning again, finds the first "#", and s[i:j] is empty for the second string. Then int("") raises a ValueError.
Read all the digits with int(s[i:j]). A string of 10 or more characters has a length with two or more digits. int(s[i]) reads only the first digit and takes too few characters.
Do not skip an empty string in encode. It is written as "0#". Skipping it makes decode return a shorter list.
The cost, and where the same idea is used
Let N be the number of strings and L the total number of characters. encode writes N prefixes and copies L characters, so it is O(N + L). decode reads each prefix once, and each slice copies the characters of one string, so it is also O(N + L). The message holds O(N + L) characters, so the space is O(N + L).
decode never scans the text of a string to find its end. It jumps over the text with i = j + 1 + length. That is why the text can hold any character.
The same idea is used in network formats. The Content-Length header of HTTP/1.1 states the size of the body before the body, so the receiver knows where the message ends.
The separator is a choice. Any character that is not a digit would work in place of "#". The important rule is that the length ends at a character that digits cannot contain.
60-Second Pitch
"The strings can hold any character, so no separator is safe. I write the size before the data: str(len(s)) + "#" + s. In decode, i is always on the first digit of a length. The first "#" from i ends the length, because digits never contain it. Then I take exactly length characters and jump i past them without reading them. So a "#" or a digit inside a string is never read as format. Empty strings work too, as "0#". The time and the space are O(N + L)."
Common Questions
- Why not join the strings with a separator?
A string can hold any character, so it can hold the separator too.
decodecannot tell a separator inside a string from a real one. For["4#ab", "", "#"], a split on"#"gives five strings.- Why does the length come before the text?
The reader must know where a piece ends before it reads the piece. With the length first,
decodecounts characters and never searches the text for an end marker.- Why is the first
"#"fromialways the end of the length? The length is written with digits, and a digit is never
"#".iis on the first digit of a length, so the first"#"fromiis the one thatencodewrote after the length.- How are empty strings handled?
encodewrites"0#"for an empty string.decodereads the length 0, takes no characters and appends"". Skipping empty strings inencodewould lose them.- What are the time and space complexity?
O(N + L) time and O(N + L) space, where
Nis the number of strings andLis the total number of characters. Each prefix and each character is handled a constant number of times.
SWE Reasoning
Spot it
- A list of strings must travel as one string and come back exactly.
- The strings may hold any character, so no separator can be kept out of them.
- Empty strings are allowed and must come back.
- The format is read from left to right, and each piece must say how long it is.
decodereceives only the encoded message, so it cannot use anything else thatencodeknew.
The invariant, step by step
encodewritesstr(len(s)) + "#" + sfor each string and joins the pieces.decodestarts withi = 0, which is the first digit of the first length.j = s.index("#", i)is the end of the length, because digits never contain"#".length = int(s[i:j])is the size of the text.s[j + 1 : j + 1 + length]is exactly the text.i = j + 1 + lengthmoves to the next length. The text is never read for format, so a"#"or a digit inside it is safe.- The loop ends when
ireacheslen(s), andstrsholds the original list.
Traps
- Joining with a separator.
["4#ab", "", "#"]is split into five strings. - Searching for the next
"#"to find the end of the text. A"#"inside the text ends it too early. - Skipping empty strings. An empty string must be written as
"0#". s.index("#")withouti. The search finds the first"#"again andint("")raises aValueError.int(s[i])for the length. A length of 10 or more has several digits.