Builds on Combinations, which you haven’t finished yet.
String Partitioning Backtracking
Given a string s, cut it into consecutive pieces so that every piece reads the same forwards and backwards (a palindrome). Return every distinct way to cut s this way.
"aa" is a palindrome, so it may stay together; "aab" and "ab" are not, so no other cut works.String Partitioning
string s ➔ valid prefix check ➔ recurse on suffix starting end + 1| 1 | from typing import Callable, List |
| 2 | |
| 3 | |
| 4 | def split_string(s: str, is_valid_piece: Callable[[List[str], int, int], bool]) -> List[List[str]]: |
| 5 | """String Partitioning: every way to cut s into pieces, where each piece s[start:end + 1] passes is_valid_piece. |
| 6 | is_valid_piece(path, start, end) checks the piece from index start to index end, both included. |
| 7 | path holds the pieces cut before it, so the check can compare with them (Additive Number, unique pieces). |
| 8 | Precondition: whether a piece is valid depends only on path and on the piece itself. |
| 9 | Expression Add Operators does not fit, because it also chooses an operator between pieces. |
| 10 | N = len(s). B = the calls to backtrack. I = the loop steps over all calls. G = the splits saved. |
| 11 | T = the cost of one is_valid_piece call. |
| 12 | Time: O(I * T + (B + G) * N) | Space: O(N) path + recursion stack, output not counted |
| 13 | """ |
| 14 | results: List[List[str]] = [] |
| 15 | path: List[str] = [] |
| 16 | |
| 17 | def backtrack(start: int) -> None: |
| 18 | # 1. Save a Complete Split: |
| 19 | # start is the first index no piece covers yet, so s is fully cut only when |
| 20 | # start reaches len(s); a split saved earlier leaves the end of s unused. |
| 21 | if start == len(s): |
| 22 | results.append(list(path)) |
| 23 | return |
| 24 | |
| 25 | for end in range(start, len(s)): |
| 26 | # 2. Choose, Explore, Un-choose, One First Piece at a Time: |
| 27 | # is_valid_piece checks the candidate piece s[start:end + 1]; trying every |
| 28 | # end from start builds each split exactly once, since a split has exactly |
| 29 | # one first piece. |
| 30 | if is_valid_piece(path, start, end): |
| 31 | path.append(s[start:end + 1]) |
| 32 | backtrack(end + 1) |
| 33 | path.pop() |
| 34 | |
| 35 | backtrack(0) |
| 36 | return results |
path, joined in order, spell exactly s[:start], and each piece passed is_palindrome.Every split is a first piece followed by a split of the rest, so at start try each end, and when is_palindrome(start, end) holds, append s[start:end + 1] to path and recurse on end + 1. Each split has exactly one first piece, so trying every end in turn builds every split once and never twice. The trap is where to save: only when start == len(s), because a path saved earlier leaves the end of s unused.
See it run
String Partitioning on a string, step by step
start 0end -path []saved 0
The first row is the letters of s. The second row marks a cut before a letter with |. The third row holds the pieces of path, in order.
piecethe piece s[start:end + 1] that is being tested, and its slot in path once appendedin patha piece that is in path nowsaveda complete split, copied into resultsundoa piece that path.pop() has just removed
Start: s = "aab" has 3 letters, path is empty, and backtrack(0) begins.
Gotcha 1 of 4
- The trap
Gotcha 1: Saving
pathbeforestartreacheslen(s)Mistakeresults.append(list(path)) if start == len(s): returnFixif start == len(s): results.append(list(path)) returnWhat happens:
startis the first index that no piece covers yet. Whilestart < len(s), the pieces inpathleave the end ofsunused. Saving on every call also saves those partial splits, such as["a"]and["a", "a"].Example: s = "aab"Mistake: returns [[], ['a'], ['a', 'a'], ['a', 'a', 'b'], ['aa'], ['aa', 'b']]Fix: returns [['a', 'a', 'b'], ['aa', 'b']]
- Only the number of ways to cut the string is asked, as in Decode Ways (LC 91), not the cuts themselves: the same
startis reached again and again, so one stored count perstartreplaces listing every split. See Memoization
Deep Dive
A split is one first piece, then a split of the rest
Combinations already shows the start index: the loop only picks from start onward, so each result is built in one order. This card changes one thing. The pieces must cover s from the first letter to the last, with no gap and no overlap. So the next call starts at end + 1, the first letter after the piece.
Every split of s has exactly one first piece. If the first piece is s[start:end + 1], the rest of the split is a split of s[end + 1:]. The loop tries every end from start. Each try fixes the first piece, and the recursive call lists every way to split the rest. So every split is built once, and no split is built twice.
A string of length N has N - 1 places where a cut may go. Each place is cut or not cut, so there are at most 2^(N - 1) splits. For s = "aaaa", every piece is a palindrome, so all 2^3 = 8 splits are valid. For s = "aaaaaaaa", there are 128.
Example: for s = "abba", the answer is [["a","b","b","a"],["a","bb","a"],["abba"]]. For s = "abc", only one split works: [["a","b","c"]].
One trace: when path is saved, and what the undo does
The board replays partition("aab"). The answer is [["a","a","b"],["aa","b"]]. The first row holds the letters of s. The second row shows a cut before a letter. The third row is path.
backtrack(0) tries end = 0. The piece "a" is a palindrome, so it is appended and backtrack(1) runs. In the same way, "a" and then "b" are appended, and backtrack(3) starts with start = 3 = len(s). The pieces cover all of s, so ["a", "a", "b"] is saved. This is the step marked as the trap on the board.
Then path.pop() removes "b", and the call for start = 1 tries end = 2. The piece "ab" is not a palindrome, so nothing is appended. After one more pop, backtrack(0) tries end = 1. The piece "aa" is appended, then "b", and ["aa", "b"] is saved. The last try, "aab", is not a palindrome.
In all, 6 calls of backtrack run, the loops take 7 steps, and 7 palindrome checks are made. Only 2 of the 6 calls have start == len(s), and only those 2 save.
Example: if the code saved on every call, partition("aab") would return [[], ["a"], ["a", "a"], ["a", "a", "b"], ["aa"], ["aa", "b"]]. The extra lists are partial splits that leave the end of s unused.
The piece check can read path, and the check changes with the problem
The template takes is_valid_piece(path, start, end). The loop never changes. Only this check changes from one problem to the next. It receives path so a check can compare the new piece with the pieces before it.
In Palindrome Partitioning (LC 131), the check reads only the piece: is_palindrome(start, end). In Restore IP Addresses (LC 93), the check is that the piece is "0" or has no leading zero, and its value is at most 255. The call also needs exactly 4 pieces. For s = "25525511135", the answer is ["255.255.11.135", "255.255.111.35"].
In Split a String Into the Max Number of Unique Substrings (LC 1593), the check reads path: the piece must not already be in path. The answer is the largest len(path) seen at a save. For s = "ababccc", it is 5. In Additive Number (LC 306), the check compares the piece with the sum of the last two pieces in path.
The template does not fit Expression Add Operators (LC 282). That problem also chooses an operator between the pieces, so one cut has more than one choice.
Example: if the check fails for every end at some start, the loop ends and the call returns without a save. That branch is cut off. For s = "abc", partition makes 4 calls and 6 palindrome checks, and it saves 1 split.
The cost: calls and loop steps times the cost of one check
The card's complexity line is O(I * T + (B + G) * N). B is the number of backtrack calls, I is the number of loop steps over all calls, and G is the number of splits saved. T is the cost of one check, and N is len(s).
For s = "aaaa", B = 16 and I = 15, and each loop step makes one palindrome check. For s = "aaaaaaaa", B = 256, I = 255 and G = 128. The numbers double when the string gets one letter longer, so the cost grows as 2^N.
One call of is_palindrome walks the piece and costs O(N). That gives O(N * 2^N) time for Palindrome Partitioning. The stack and path use O(N) space, and the saved output is not counted.
The same pair (start, end) is checked in many branches. A table is_pal[i][j], built once in O(N^2) time, makes each check cost O(1). Each saved split is still copied with list(path), which costs O(N). So the worst case stays O(N * 2^N), and the table removes the repeated work only.
Example: if only the number of splits is asked, as in Decode Ways (LC 91), do not list them. The same start is reached again and again, so one stored count per start is enough.
60-Second Pitch
"A split has exactly one first piece, so I fix that piece and split the rest. At start, I try every end. If s[start:end + 1] passes the check, I append it to path, call backtrack(end + 1), and then pop it. I save path only when start == len(s), because only then do the pieces cover all of s. I save a copy, not path itself. Each split is built once. The number of splits is at most 2^(N - 1), and each check costs O(N), so the time is O(N * 2^N). With a table of palindrome answers, each check is O(1). If the question asks only for a count, I would use one stored count per start instead of listing the splits."
Common Questions
- Why does the recursive call use
end + 1and notstart + 1? The piece
s[start:end + 1]is already used. The next piece must begin at the first unused letter, which isend + 1. Usingstart + 1would make pieces overlap, and the pieces would no longer spells.- Why is
pathsaved only whenstart == len(s)? startis the first letter that no piece covers. Before it reacheslen(s), the pieces inpathleave the end ofsunused. For"aab", saving on every call returns 6 lists instead of the 2 splits.- How do you speed up the palindrome check?
Build a table
is_pal[i][j]once. A pieces[i:j + 1]is a palindrome whens[i] == s[j]and the insideis_pal[i + 1][j - 1]is a palindrome, or the inside is empty or one letter. The table costs O(N^2), and each check then costsO(1). The saved output is still copied, so the worst case stays O(N * 2^N).- What changes for Restore IP Addresses (LC 93)?
Only the check and the stop rule. Each piece has 1 to 3 digits, is "0" or has no leading zero, and is at most 255. The save needs
len(path) == 4andstart == len(s). The loop tries at most 3 values ofend, so the search is small.- When is a count enough, and which technique do you use then?
If the question asks how many splits exist, as in Decode Ways (LC 91), the same
startis reached again and again. Store the count for eachstartand reuse it. That is memoization, and it takesO(N)states instead of listing 2^(N - 1) splits.
SWE Reasoning
Spot it
- A string must be cut into pieces, and each piece must pass a test: a palindrome, a valid IP part, a dictionary word, an unused piece.
- The pieces, joined in order, must give back the whole string with nothing left over.
- The question asks for every split, or for the best split found by trying all of them, and
Nis small, about 16 to 20. - The pieces are substrings in a fixed order. They are not a choice of items from a set.
- The test for a piece depends only on the piece and on the pieces before it.
The invariant, step by step
backtrack(start)is called when the pieces inpath, joined in order, spell exactlys[:start], and each piece passedis_palindrome.- If
start == len(s), the pieces spell all ofs. The call saveslist(path)and returns. - Otherwise the loop tries each
endfromstart. The candidate piece iss[start:end + 1]. - If the piece passes, it is appended to
path, so the pieces now spells[:end + 1]. The callbacktrack(end + 1)keeps the invariant. - After the call,
path.pop()removes the piece.pathis again exactly as it was before the append, and the loop tries the nextend. - A split has one first piece, so each split is built once. A piece that fails is never appended, and its branch is never entered.
Traps
- Saving before
startreacheslen(s). Saved lists include partial splits. For"aab", the result has 6 lists instead of 2, and one of them is empty. - Slicing
s[start:end]. The slice stops beforeend, so each piece loses its last letter. For"aab", the result is[["", "", ""], ["a", ""]]. - Saving
pathitself.pathkeeps changing, so the saved list ends up empty. Savelist(path). - Skipping
path.pop(). The next piece is appended after the old one, and the pieces no longer spells[:start]. - A leading zero in Restore IP Addresses (LC 93). For
s = "10001", a check that only testsint(part) <= 255also returns"1.0.0.01". The right answer is["10.0.0.1"]. - Checking the same pair again and again. Each check costs
O(N). A tableis_pal[i][j]makes itO(1).
Practice
Builds on Combinations, which you haven’t finished yet.
String Partitioning Backtracking
Given a string s, cut it into consecutive pieces so that every piece reads the same forwards and backwards (a palindrome). Return every distinct way to cut s this way.
"aa" is a palindrome, so it may stay together; "aab" and "ab" are not, so no other cut works.String Partitioning
string s ➔ valid prefix check ➔ recurse on suffix starting end + 1| 1 | from typing import Callable, List |
| 2 | |
| 3 | |
| 4 | def split_string(s: str, is_valid_piece: Callable[[List[str], int, int], bool]) -> List[List[str]]: |
| 5 | """String Partitioning: every way to cut s into pieces, where each piece s[start:end + 1] passes is_valid_piece. |
| 6 | is_valid_piece(path, start, end) checks the piece from index start to index end, both included. |
| 7 | path holds the pieces cut before it, so the check can compare with them (Additive Number, unique pieces). |
| 8 | Precondition: whether a piece is valid depends only on path and on the piece itself. |
| 9 | Expression Add Operators does not fit, because it also chooses an operator between pieces. |
| 10 | N = len(s). B = the calls to backtrack. I = the loop steps over all calls. G = the splits saved. |
| 11 | T = the cost of one is_valid_piece call. |
| 12 | Time: O(I * T + (B + G) * N) | Space: O(N) path + recursion stack, output not counted |
| 13 | """ |
| 14 | results: List[List[str]] = [] |
| 15 | path: List[str] = [] |
| 16 | |
| 17 | def backtrack(start: int) -> None: |
| 18 | # 1. Save a Complete Split: |
| 19 | # start is the first index no piece covers yet, so s is fully cut only when |
| 20 | # start reaches len(s); a split saved earlier leaves the end of s unused. |
| 21 | if start == len(s): |
| 22 | results.append(list(path)) |
| 23 | return |
| 24 | |
| 25 | for end in range(start, len(s)): |
| 26 | # 2. Choose, Explore, Un-choose, One First Piece at a Time: |
| 27 | # is_valid_piece checks the candidate piece s[start:end + 1]; trying every |
| 28 | # end from start builds each split exactly once, since a split has exactly |
| 29 | # one first piece. |
| 30 | if is_valid_piece(path, start, end): |
| 31 | path.append(s[start:end + 1]) |
| 32 | backtrack(end + 1) |
| 33 | path.pop() |
| 34 | |
| 35 | backtrack(0) |
| 36 | return results |
path, joined in order, spell exactly s[:start], and each piece passed is_palindrome.Every split is a first piece followed by a split of the rest, so at start try each end, and when is_palindrome(start, end) holds, append s[start:end + 1] to path and recurse on end + 1. Each split has exactly one first piece, so trying every end in turn builds every split once and never twice. The trap is where to save: only when start == len(s), because a path saved earlier leaves the end of s unused.
See it run
String Partitioning on a string, step by step
start 0end -path []saved 0
The first row is the letters of s. The second row marks a cut before a letter with |. The third row holds the pieces of path, in order.
piecethe piece s[start:end + 1] that is being tested, and its slot in path once appendedin patha piece that is in path nowsaveda complete split, copied into resultsundoa piece that path.pop() has just removed
Start: s = "aab" has 3 letters, path is empty, and backtrack(0) begins.
Gotcha 1 of 4
- The trap
Gotcha 1: Saving
pathbeforestartreacheslen(s)Mistakeresults.append(list(path)) if start == len(s): returnFixif start == len(s): results.append(list(path)) returnWhat happens:
startis the first index that no piece covers yet. Whilestart < len(s), the pieces inpathleave the end ofsunused. Saving on every call also saves those partial splits, such as["a"]and["a", "a"].Example: s = "aab"Mistake: returns [[], ['a'], ['a', 'a'], ['a', 'a', 'b'], ['aa'], ['aa', 'b']]Fix: returns [['a', 'a', 'b'], ['aa', 'b']]
- Only the number of ways to cut the string is asked, as in Decode Ways (LC 91), not the cuts themselves: the same
startis reached again and again, so one stored count perstartreplaces listing every split. See Memoization
Deep Dive
A split is one first piece, then a split of the rest
Combinations already shows the start index: the loop only picks from start onward, so each result is built in one order. This card changes one thing. The pieces must cover s from the first letter to the last, with no gap and no overlap. So the next call starts at end + 1, the first letter after the piece.
Every split of s has exactly one first piece. If the first piece is s[start:end + 1], the rest of the split is a split of s[end + 1:]. The loop tries every end from start. Each try fixes the first piece, and the recursive call lists every way to split the rest. So every split is built once, and no split is built twice.
A string of length N has N - 1 places where a cut may go. Each place is cut or not cut, so there are at most 2^(N - 1) splits. For s = "aaaa", every piece is a palindrome, so all 2^3 = 8 splits are valid. For s = "aaaaaaaa", there are 128.
Example: for s = "abba", the answer is [["a","b","b","a"],["a","bb","a"],["abba"]]. For s = "abc", only one split works: [["a","b","c"]].
One trace: when path is saved, and what the undo does
The board replays partition("aab"). The answer is [["a","a","b"],["aa","b"]]. The first row holds the letters of s. The second row shows a cut before a letter. The third row is path.
backtrack(0) tries end = 0. The piece "a" is a palindrome, so it is appended and backtrack(1) runs. In the same way, "a" and then "b" are appended, and backtrack(3) starts with start = 3 = len(s). The pieces cover all of s, so ["a", "a", "b"] is saved. This is the step marked as the trap on the board.
Then path.pop() removes "b", and the call for start = 1 tries end = 2. The piece "ab" is not a palindrome, so nothing is appended. After one more pop, backtrack(0) tries end = 1. The piece "aa" is appended, then "b", and ["aa", "b"] is saved. The last try, "aab", is not a palindrome.
In all, 6 calls of backtrack run, the loops take 7 steps, and 7 palindrome checks are made. Only 2 of the 6 calls have start == len(s), and only those 2 save.
Example: if the code saved on every call, partition("aab") would return [[], ["a"], ["a", "a"], ["a", "a", "b"], ["aa"], ["aa", "b"]]. The extra lists are partial splits that leave the end of s unused.
The piece check can read path, and the check changes with the problem
The template takes is_valid_piece(path, start, end). The loop never changes. Only this check changes from one problem to the next. It receives path so a check can compare the new piece with the pieces before it.
In Palindrome Partitioning (LC 131), the check reads only the piece: is_palindrome(start, end). In Restore IP Addresses (LC 93), the check is that the piece is "0" or has no leading zero, and its value is at most 255. The call also needs exactly 4 pieces. For s = "25525511135", the answer is ["255.255.11.135", "255.255.111.35"].
In Split a String Into the Max Number of Unique Substrings (LC 1593), the check reads path: the piece must not already be in path. The answer is the largest len(path) seen at a save. For s = "ababccc", it is 5. In Additive Number (LC 306), the check compares the piece with the sum of the last two pieces in path.
The template does not fit Expression Add Operators (LC 282). That problem also chooses an operator between the pieces, so one cut has more than one choice.
Example: if the check fails for every end at some start, the loop ends and the call returns without a save. That branch is cut off. For s = "abc", partition makes 4 calls and 6 palindrome checks, and it saves 1 split.
The cost: calls and loop steps times the cost of one check
The card's complexity line is O(I * T + (B + G) * N). B is the number of backtrack calls, I is the number of loop steps over all calls, and G is the number of splits saved. T is the cost of one check, and N is len(s).
For s = "aaaa", B = 16 and I = 15, and each loop step makes one palindrome check. For s = "aaaaaaaa", B = 256, I = 255 and G = 128. The numbers double when the string gets one letter longer, so the cost grows as 2^N.
One call of is_palindrome walks the piece and costs O(N). That gives O(N * 2^N) time for Palindrome Partitioning. The stack and path use O(N) space, and the saved output is not counted.
The same pair (start, end) is checked in many branches. A table is_pal[i][j], built once in O(N^2) time, makes each check cost O(1). Each saved split is still copied with list(path), which costs O(N). So the worst case stays O(N * 2^N), and the table removes the repeated work only.
Example: if only the number of splits is asked, as in Decode Ways (LC 91), do not list them. The same start is reached again and again, so one stored count per start is enough.
60-Second Pitch
"A split has exactly one first piece, so I fix that piece and split the rest. At start, I try every end. If s[start:end + 1] passes the check, I append it to path, call backtrack(end + 1), and then pop it. I save path only when start == len(s), because only then do the pieces cover all of s. I save a copy, not path itself. Each split is built once. The number of splits is at most 2^(N - 1), and each check costs O(N), so the time is O(N * 2^N). With a table of palindrome answers, each check is O(1). If the question asks only for a count, I would use one stored count per start instead of listing the splits."
Common Questions
- Why does the recursive call use
end + 1and notstart + 1? The piece
s[start:end + 1]is already used. The next piece must begin at the first unused letter, which isend + 1. Usingstart + 1would make pieces overlap, and the pieces would no longer spells.- Why is
pathsaved only whenstart == len(s)? startis the first letter that no piece covers. Before it reacheslen(s), the pieces inpathleave the end ofsunused. For"aab", saving on every call returns 6 lists instead of the 2 splits.- How do you speed up the palindrome check?
Build a table
is_pal[i][j]once. A pieces[i:j + 1]is a palindrome whens[i] == s[j]and the insideis_pal[i + 1][j - 1]is a palindrome, or the inside is empty or one letter. The table costs O(N^2), and each check then costsO(1). The saved output is still copied, so the worst case stays O(N * 2^N).- What changes for Restore IP Addresses (LC 93)?
Only the check and the stop rule. Each piece has 1 to 3 digits, is "0" or has no leading zero, and is at most 255. The save needs
len(path) == 4andstart == len(s). The loop tries at most 3 values ofend, so the search is small.- When is a count enough, and which technique do you use then?
If the question asks how many splits exist, as in Decode Ways (LC 91), the same
startis reached again and again. Store the count for eachstartand reuse it. That is memoization, and it takesO(N)states instead of listing 2^(N - 1) splits.
SWE Reasoning
Spot it
- A string must be cut into pieces, and each piece must pass a test: a palindrome, a valid IP part, a dictionary word, an unused piece.
- The pieces, joined in order, must give back the whole string with nothing left over.
- The question asks for every split, or for the best split found by trying all of them, and
Nis small, about 16 to 20. - The pieces are substrings in a fixed order. They are not a choice of items from a set.
- The test for a piece depends only on the piece and on the pieces before it.
The invariant, step by step
backtrack(start)is called when the pieces inpath, joined in order, spell exactlys[:start], and each piece passedis_palindrome.- If
start == len(s), the pieces spell all ofs. The call saveslist(path)and returns. - Otherwise the loop tries each
endfromstart. The candidate piece iss[start:end + 1]. - If the piece passes, it is appended to
path, so the pieces now spells[:end + 1]. The callbacktrack(end + 1)keeps the invariant. - After the call,
path.pop()removes the piece.pathis again exactly as it was before the append, and the loop tries the nextend. - A split has one first piece, so each split is built once. A piece that fails is never appended, and its branch is never entered.
Traps
- Saving before
startreacheslen(s). Saved lists include partial splits. For"aab", the result has 6 lists instead of 2, and one of them is empty. - Slicing
s[start:end]. The slice stops beforeend, so each piece loses its last letter. For"aab", the result is[["", "", ""], ["a", ""]]. - Saving
pathitself.pathkeeps changing, so the saved list ends up empty. Savelist(path). - Skipping
path.pop(). The next piece is appended after the old one, and the pieces no longer spells[:start]. - A leading zero in Restore IP Addresses (LC 93). For
s = "10001", a check that only testsint(part) <= 255also returns"1.0.0.01". The right answer is["10.0.0.1"]. - Checking the same pair again and again. Each check costs
O(N). A tableis_pal[i][j]makes itO(1).