The longest common subsequence
A DP state can be a position in a list, a cell of a grid, or a number of items together with a capacity. Most problems in this lesson compare two strings: they ask how much the strings have in common, or how many changes turn one into the other. The best-known of them asks for the longest common subsequence, or LCS for short.
A subsequence of a string is what remains after deleting some of its characters, possibly none, and keeping the rest in order. ple is a subsequence of plate: delete the a and the t. pea is not, because in plate the a comes before the e. A common subsequence of two strings is a subsequence of both. ple is also a subsequence of apple, so it is a common subsequence of plate and apple.
You get two strings, text1 and text2. Return the length of their longest common subsequence: the longest string that is a subsequence of both. If they have none, return 0.
A subsequence of a string keeps some of its characters, possibly none or all, in their original order and deletes the rest.
Constraints
- Each string has 1 to 1,000 characters
- Only lowercase English letters
Sample 1 · Input
text1 = "abcde", text2 = "ace"
Output
3
Sample 2 · Input
text1 = "abc", text2 = "abc"
Output
3
Sample 3 · Input
text1 = "abc", text2 = "def"
Output
0
In the first sample ace is a subsequence of abcde, so the whole second string is a common subsequence, of length 3. In the third sample the strings share no letter, and their only common subsequence is the empty one.
Our example for this problem is plate and apple. Their common subsequence ple has length 3, and none is longer. The only other letter the two words share is a. In plate the a comes after the p and the l, and in apple it comes before them, so a common subsequence that uses the a can use neither of those letters. It is then a or ae, two characters at most.
A program could list every subsequence of the first string and check each one against the second. Every character is either kept or deleted, so a string of characters has ways to choose a subsequence: 32 for plate, 1,048,576 for a string of 20 characters, and a number with 302 digits for a string of 1,000 characters, the longest this problem allows.
A state for each pair of prefixes
A prefix of a string is its first few characters. plate has six prefixes: the empty string, p, pl, pla, plat and plate itself. Word Break used the prefixes of one string as its states. With two strings, a state is a pair of prefixes, one from each string. As in Word Break, the plan is to decide what happens at the end of the strings and leave the rest to a smaller question. Taking the last character away from a prefix leaves a shorter prefix, so the smaller questions are again about pairs of prefixes.
Call the strings a and b, with lengths and . Let dp[i][j] be the length of the longest common subsequence of the first characters of a and the first characters of b. There is one state for each from 0 to and each from 0 to , and the answer is dp[n][m].
For the transition, look at the last character of each prefix. Positions in a string are numbered from 0, so the last of the first characters of a is a[i - 1], and the last of the first characters of b is b[j - 1]. There are two cases:
- The two characters are equal. A longest common subsequence can then end with that character, taken from the end of both prefixes. What comes before it is a common subsequence of the two prefixes without their last characters, and the longest of those has length
dp[i - 1][j - 1]. - The two characters differ. A common subsequence cannot end with both of them, so it leaves at least one of them out. If it leaves out
a[i - 1], it is a common subsequence of the first characters ofaand the first characters ofb, and the longest of those has lengthdp[i - 1][j]. If it leaves outb[j - 1], the same reasoning givesdp[i][j - 1]. The transition keeps the larger of these two candidates.
The base cases are the states in which one prefix is empty. The only subsequence of an empty string is the empty one, so dp[0][j] and dp[i][0] are 0. Every other entry reads the entry above it, the entry to its left, or the entry diagonally up and to the left. These are the three neighbours that Maximal Square reads, and the evaluation order is the same: one row at a time from the top, each row from left to right.
Here is the finished table for plate and apple, with ∅ for the empty prefix:
plate, and the labels under the table are the characters of apple. The entry in row t and column l is for the prefixes plat and appl.The bottom-right entry is 3, the length of ple.
On the left the prefixes are pl and app. Their last characters, l and p, differ, so the entry is the larger of the entry above it, for p and app, and the entry to its left, for pl and ap. Both hold 1. On the right the prefixes are pl and appl. Both end in l, so the entry is 1 more than the diagonal entry, for p and app, which makes 2.
Fill the table with two loops
The program creates a table of rows and columns that holds 0 everywhere, which takes care of the base cases, and then fills the other entries row by row.
def lcs_length(a, b):
n, m = len(a), len(b)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[n][m]
print(lcs_length("plate", "apple"))
print(lcs_length("abcde", "ace"))
print(lcs_length("abc", "def"))Prints 3, 3 and 0.
The table has entries, about a million for two strings of 1,000 characters, and each entry takes a fixed number of steps.
Deeper read: why two equal last characters can be matched
When the two prefixes end in the same character, the transition takes the diagonal entry plus 1 and does not look at the entries above and to the left. This is safe because some longest common subsequence of the two prefixes ends with those two characters matched to each other.
Take any longest common subsequence of the two prefixes. If it uses neither of the two last characters, the shared character could be added to its end, so it would not be a longest one. If it uses the last character of one prefix, that character has to be the last one of the subsequence, because nothing in that prefix comes after it. The character it is matched with in the other prefix can then be swapped for that prefix's last character, which is the same letter and comes after everything else the subsequence uses.
Either way, some longest common subsequence ends with the two last characters matched. Without that pair it is a common subsequence of the two shorter prefixes, so its length is at most the diagonal entry plus 1, and the first case of the transition shows that this length is reached.
Worked example
Predict each entry yourself
The trace fills the same table one entry at a time. Switch on Predict the next step to work out each entry before it appears.
dp[i][j] is the longest common subsequence length for the first i and j letters. An empty prefix has length zero.
Change the example input
Current result: 3
Rebuild the subsequence from the table
The table gives the length of the longest common subsequence and not the subsequence itself. We can rebuild it the way we rebuilt the cheapest path through a grid, by walking back from the answer. At each entry, the two characters and the neighbouring entries tell us which case of the transition produced it.
The walk starts at the bottom-right entry, with and , and repeats one step until or reaches 0:
- If
a[i - 1]equalsb[j - 1], that character belongs to the subsequence. Write it down and move diagonally, to and . - Otherwise the entry was copied from the larger of its two neighbours. Move up, to , when the entry above is at least as large as the entry to the left, and move left, to , when the entry to the left is larger.
The characters are written down from last to first, so the result is reversed at the end. For plate and apple the walk visits the highlighted entries:
The walk starts on the 3. Both words end in e, so it writes down e and moves diagonally to the 2 in row t. There the characters are t and l. They differ, and the entry above, 2, is at least as large as the entry to the left, 1, so the walk moves up. The same happens in row a. In row l the characters are l and l, and in row p they are p and p, so two diagonal steps write down l and then p. The walk has reached the top row with e, l and p written down, and reversing them gives ple.
def lcs(a, b):
n, m = len(a), len(b)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
letters = []
i, j = n, m
while i > 0 and j > 0:
if a[i - 1] == b[j - 1]:
letters.append(a[i - 1])
i -= 1
j -= 1
elif dp[i - 1][j] >= dp[i][j - 1]:
i -= 1
else:
j -= 1
return "".join(reversed(letters))
print(lcs("plate", "apple"))
print(lcs("abcde", "ace"))Prints ple and ace.
Every step lowers or , so the walk takes at most steps. When the entry above and the entry to the left are equal, either move is correct, and the two moves can lead to different subsequences of the same length.
Step through the fill and the walk
The widget fills the table for plate and apple one entry at a time and shows which entries each one reads. On its last step it walks back and spells the subsequence. Change the words to abcde and ace, the first sample, and the walk spells ace.
Two problems solved by the LCS table
The next problem never mentions a common subsequence, and the LCS table still answers it.
You get two words, word1 and word2. In one step you delete exactly one character from either word. Return the fewest steps that make the two words equal.
Constraints
- Each word has 1 to 500 characters
- Only lowercase English letters
Sample 1 · Input
word1 = "sea", word2 = "eat"
Output
2
Sample 2 · Input
word1 = "leetcode", word2 = "etco"
Output
4
Deleting the s of sea and the t of eat leaves ea in both words after two steps.
The string that is left at the end was made from each word by deletions alone, so it is a common subsequence of the two words. If it has length , the first word lost characters and the second lost , where and are the lengths of the words. The number of steps is smallest when is largest, which happens when a longest common subsequence is left:
For sea and eat the longest common subsequence is ea, and the answer is . In the second sample etco is a subsequence of leetcode, so is 4 and the answer is . The program is the LCS program with this formula in its last line.
Deeper read: the shortest common supersequence
A second problem of this kind asks for a string, and the walk back builds it.
You get two strings, str1 and str2. Return the shortest string that has both of them as subsequences. If several shortest strings exist, return any one of them.
Constraints
- Each string has 1 to 1,000 characters
- Only lowercase English letters
Sample 1 · Input
str1 = "abac", str2 = "cab"
Output
"cabac"
Sample 2 · Input
str1 = "aaaaaaaa", str2 = "aaaaaaaa"
Output
"aaaaaaaa"
cabac has abac as a subsequence (delete the first c) and cab as well (its first three characters).
A common supersequence of two strings is a string that has both of them as subsequences, as cabac does here. Some of its characters can serve both strings at once, and read in order those characters spell a common subsequence of the two. Each of them is written once, and every other character of either string needs a place of its own. So a supersequence whose shared characters have length has at least characters, and the bound is lowest when the shared characters form a longest common subsequence. For abac and cab that is ab, which gives at least characters.
The walk back builds a string of exactly that length when every step writes a character. A diagonal step writes the shared character once. A step up passes over a[i - 1], which is not part of the common subsequence but still has to appear, so the step writes it. A step to the left writes b[j - 1] for the same reason. When one string runs out, the rest of the other is written. As before, the characters come out from last to first.
def shortest_common_supersequence(a, b):
n, m = len(a), len(b)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
out = []
i, j = n, m
while i > 0 and j > 0:
if a[i - 1] == b[j - 1]:
out.append(a[i - 1])
i -= 1
j -= 1
elif dp[i - 1][j] >= dp[i][j - 1]:
out.append(a[i - 1])
i -= 1
else:
out.append(b[j - 1])
j -= 1
out.extend(reversed(a[:i]))
out.extend(reversed(b[:j]))
return "".join(reversed(out))
print(shortest_common_supersequence("abac", "cab"))
print(shortest_common_supersequence("aaaaaaaa", "aaaaaaaa"))Prints cabac and aaaaaaaa, the two samples.
Edit distance
The longest common subsequence measures what two strings share. The edit distance measures how far apart they are: it is the smallest number of operations that turn one string into the other, where an operation inserts one character, deletes one character, or replaces one character with another.
You get two words, word1 and word2. One operation inserts a character, deletes a character or replaces a character with another. Return the fewest operations that turn word1 into word2.
Constraints
- Each word has 0 to 500 characters
- Only lowercase English letters
Sample 1 · Input
word1 = "horse", word2 = "ros"
Output
3
Sample 2 · Input
word1 = "intention", word2 = "execution"
Output
5
Three operations turn horse into ros: replace the h with an r (rorse), delete the second r (rose) and delete the e (ros). Two operations are not enough. ros is two characters shorter than horse, so both would have to be deletions, and ros is not a subsequence of horse.
The states are the same pairs of prefixes, with a different value. Let dp[i][j] be the smallest number of operations that turn the first characters of a into the first characters of b. The answer is dp[n][m].
To find the transition, it helps to draw a sequence of operations as an alignment. Write the two strings one above the other, leave a gap in the top row for each inserted character and a gap in the bottom row for each deleted one, and put each replaced character above the character that replaces it. Here are the three operations above as an alignment:
A column that holds the same character twice costs nothing. Every other column is one operation: two different characters are a replacement, a character above a gap is a deletion, and a gap above a character is an insertion. The number of operations is the number of columns that do not hold the same character twice.
Now take a cheapest alignment of the first characters of a with the first characters of b, and look at its last column. The columns before it align two shorter prefixes, and they must be a cheapest alignment of those prefixes: if a cheaper one existed, putting the last column back on it would give a cheaper alignment of the whole. So once the last column is chosen, the rest costs an entry already in the table. The last column has three possible forms:
a[i - 1]above a gap: the last character ofais deleted. The rest aligns the first characters ofawith the first characters ofb, so this candidate isdp[i - 1][j] + 1.- A gap above
b[j - 1]: the last character ofbis inserted. The rest aligns the first characters ofawith the first characters ofb, so this candidate isdp[i][j - 1] + 1. a[i - 1]aboveb[j - 1]: the character is kept if the two are equal, at no cost, and replaced if they differ, at a cost of 1. The rest aligns the first characters with the first , so this candidate isdp[i - 1][j - 1]plus that cost.
The transition keeps the smallest of the three candidates. In the formula, cost is 0 when a[i - 1] equals b[j - 1] and 1 when they differ:
The base cases are no longer all 0. Turning characters into the empty string takes deletions, so dp[i][0] is , and building characters from the empty string takes insertions, so dp[0][j] is . The evaluation order is the one the LCS table used.
Here is the table for the first sample:
horse and ros. The highlighted path is the walk back from the answer.The entry for h and r, in row 1 and column 1, has three candidates. Deleting the h gives , inserting the r gives , and replacing the h with the r gives , so the entry is 1. The bottom-right entry is 3.
The walk back follows the same idea as for the LCS, and each of its steps finds one column of the alignment, from the last column to the first. From each entry it moves to a neighbour that could have produced it, one whose value plus the cost of that step equals the entry: up for a deletion, left for an insertion, diagonally for a character that was kept or replaced.
The table does not store which candidate won, and it does not need to, because each check compares numbers that are already in the table. When more than one candidate equals the entry, any of them leads to a cheapest alignment. Read from the top-left corner, the path in the figure is the alignment of horse and ros drawn above.
Fill the edit-distance table
The program writes the base cases into the first row and the first column, and takes the smallest of the three candidates for every other entry.
def edit_distance(a, b):
n, m = len(a), len(b)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1):
dp[i][0] = i
for j in range(m + 1):
dp[0][j] = j
for i in range(1, n + 1):
for j in range(1, m + 1):
cost = 0 if a[i - 1] == b[j - 1] else 1
dp[i][j] = min(dp[i - 1][j] + 1,
dp[i][j - 1] + 1,
dp[i - 1][j - 1] + cost)
return dp[n][m]
print(edit_distance("horse", "ros"))
print(edit_distance("intention", "execution"))Prints 3 and 5, the two samples.
Two words of 500 characters, the longest the problem allows, give a table of about 250,000 entries, and each entry takes a fixed number of steps.
Step through the edit-distance table
The widget fills the table for horse and ros and lists the operations on its last step. Where the two characters are equal it shows only the diagonal candidate. The Deeper read below shows why that is enough. kitten and sitting are another pair to try, and they also need 3 operations.
Deeper read: why equal characters need only the diagonal entry
When a[i - 1] equals b[j - 1], the diagonal candidate is dp[i - 1][j - 1] with nothing added, and it is never larger than the other two.
Compare it with the delete candidate, dp[i - 1][j] + 1. One way to turn the first characters of a into the first characters of b is to turn them into the first characters, in dp[i - 1][j] operations, and then delete the last one. So dp[i - 1][j - 1] is at most dp[i - 1][j] + 1. The insert candidate is handled the same way. Start again from the first characters of a, and insert a[i - 1] at their end, which gives the first characters of a in one operation. Then dp[i][j - 1] more operations turn those into the first characters of b. So dp[i - 1][j - 1] is also at most dp[i][j - 1] + 1.
Count the ways one string appears in another
The entries so far were lengths and numbers of operations. Pairs of prefixes can also hold counts, as the cells of the grid did in Unique Paths.
You get strings s and t. Count the ways to pick characters of s, keeping their order, that spell t. Two ways are different when they use different positions of s.
Constraints
- Each string has 1 to 1,000 characters
- Only English letters
- The answer fits in a 32-bit signed integer
Sample 1 · Input
s = "rabbbit", t = "rabbit"
Output
3
Sample 2 · Input
s = "babgbag", t = "bag"
Output
5
The two strings play different parts here, so we keep the problem's names for them: t is looked for inside s. In the first sample rabbbit has three b's in a row and rabbit needs two. Leaving out each of the three in turn gives 3 ways.
Let ways[i][j] be the number of ways to pick positions among the first characters of s that spell the first characters of t. The transition comes from the last of those characters, s[i - 1], which splits the ways into two groups:
- Ways that do not pick it. All their positions are among the first characters of
s, so there areways[i - 1][j]of them. - Ways that pick it. It is then the last position picked, so it spells
t[j - 1], and this group is empty unlesss[i - 1]equalst[j - 1]. The positions before it spell the first characters oftamong the first characters ofs, which can be done inways[i - 1][j - 1]ways.
No way belongs to both groups, so the two counts are added:
The first column and the first row get different values. ways[i][0] is 1 for every : the empty string is spelled in exactly one way, by picking no positions. ways[0][j] is 0 for every above 0, because nothing can be picked from an empty string.
The second sample, babgbag and bag, gives this table:
babgbag, and the labels under the table are the characters of bag.The last row belongs to the final g of babgbag, which equals the last character of bag. The last entry of that row adds the two highlighted entries in the row above: 1 way that does not pick this g, and 4 ways to spell ba in front of it. That makes 5.
def num_distinct(s, t):
n, m = len(s), len(t)
ways = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1):
ways[i][0] = 1
for i in range(1, n + 1):
for j in range(1, m + 1):
ways[i][j] = ways[i - 1][j]
if s[i - 1] == t[j - 1]:
ways[i][j] += ways[i - 1][j - 1]
return ways[n][m]
print(num_distinct("rabbbit", "rabbit"))
print(num_distinct("babgbag", "bag"))Prints 3 and 5, the two samples.
Deeper read: interleaving two strings
In the next problem the entries are yes or no, as they were in Word Break.
You get strings s1, s2 and s3. Decide whether s3 is an interleaving of s1 and s2: cut each of s1 and s2 into pieces and alternate the pieces, so that every character of both is used once and each keeps its own order.
Constraints
s1ands2have 0 to 100 characters eachs3has 0 to 200 characters- Only lowercase English letters
Sample 1 · Input
s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output
true
Sample 2 · Input
s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output
false
Sample 3 · Input
s1 = "", s2 = "", s3 = ""
Output
true
The s3 of the first sample takes aa from s1, dbbc from s2, bc from s1, a from s2 and c from s1.
An interleaving uses every character of both strings, so s3 must be exactly as long as s1 and s2 together, and the program answers false at once when the lengths do not match. Each string keeps its order, so the first characters of s3 are made of the first characters of s1 and the first characters of s2, for some and . Let ok[i][j] say whether the first characters of s1 and the first characters of s2 can be interleaved into the first characters of s3.
The last of those characters, s3[i + j - 1], came from one of the two strings:
- From
s1. Thens1[i - 1]equals it, and the characters before it are an interleaving, sook[i - 1][j]is true. - From
s2. Thens2[j - 1]equals it, andok[i][j - 1]is true.
The entry is true when at least one of the two holds. In the first row, where is 0, only the second case can apply, and in the first column only the first, so the program checks that or is above 0 before it reads the neighbour. The base case is ok[0][0], which is true: two empty strings interleave into an empty string.
def is_interleave(s1, s2, s3):
n, m = len(s1), len(s2)
if n + m != len(s3):
return False
ok = [[False] * (m + 1) for _ in range(n + 1)]
ok[0][0] = True
for i in range(n + 1):
for j in range(m + 1):
if i > 0 and ok[i - 1][j] and s1[i - 1] == s3[i + j - 1]:
ok[i][j] = True
if j > 0 and ok[i][j - 1] and s2[j - 1] == s3[i + j - 1]:
ok[i][j] = True
return ok[n][m]
print(is_interleave("aabcc", "dbbca", "aadbbcbcac"))
print(is_interleave("aabcc", "dbbca", "aadbbbaccc"))
print(is_interleave("", "", ""))Prints True, False and True, the three samples.
A simpler rule would take the next character of s3 from s1 whenever s1 can supply it. On the first sample that rule takes the first b of s3 from s1. When it reaches the ninth character, an a, s1 is used up and the next unused character of s2 is a c, so it answers false. The table keeps both possibilities for every pair of prefixes and answers true.
A state for each range: palindromes
A palindrome is a string that reads the same forwards and backwards, such as level. The last problem of the lesson has one string and asks for its longest subsequence that is a palindrome.
You get a string s. Return the length of its longest subsequence that is a palindrome, a string that reads the same forwards and backwards.
Constraints
- 1 to 1,000 characters
- Only lowercase English letters
Sample 1 · Input
s = "bbbab"
Output
4
Sample 2 · Input
s = "cbbd"
Output
2
The longest one in bbbab is bbbb, made of its four b's, and the longest one in cbbd is bb.
Try the prefix state first: the length of the longest palindromic subsequence of the first characters. A palindrome is built from the outside in: its first and last characters are equal, and what lies between them is a shorter palindrome. In bbbab the longest one, bbbb, has the first b and the last b as its outer pair. The rest of it is a palindrome chosen from bba, the characters between those two, and bba is not a prefix of bbbab. Taking the outer pair away cuts the string at both ends, so the smaller questions are about the characters from some position to some position , with both ends moving.
So the state names both ends. Let dp[l][r] be the length of the longest palindromic subsequence of the characters from position to position , with both ends included and positions numbered from 0. The answer is dp[0][n - 1]. The transition compares the two end characters the way the LCS compared two last characters:
- If
s[l]equalss[r], the two can be the first and last character of the palindrome, around the longest palindromic subsequence of the characters between them. That givesdp[l + 1][r - 1] + 2. - If they differ, the palindrome cannot start with
s[l]and end withs[r], so it leaves one of them out. That gives the larger ofdp[l + 1][r]anddp[l][r - 1].
A single character is a palindrome, so dp[l][l] is 1. A range with greater than is empty and counts as 0. The transition reads such a range when two neighbouring characters are equal, as in bb, whose entry is .
An entry reads dp[l + 1][r - 1] and dp[l + 1][r], which are in the row below it, so the rows cannot be filled from the top as before. Every entry reads ranges that are shorter than its own, and any order that finishes the shorter ranges first will do. The program lets run from down to 0, and for each lets run upward from . The row below is then complete, and so is the entry to the left.
For bbbab the table looks like this:
The whole string is the range with and . It starts and ends with b, so its entry is 2 more than the entry for the characters between them, bba. That entry holds 2, which makes 4, the expected output.
def longest_palindrome_subseq(s):
n = len(s)
dp = [[0] * n for _ in range(n)]
for l in range(n - 1, -1, -1):
dp[l][l] = 1
for r in range(l + 1, n):
if s[l] == s[r]:
dp[l][r] = dp[l + 1][r - 1] + 2
else:
dp[l][r] = max(dp[l + 1][r], dp[l][r - 1])
return dp[0][n - 1]
print(longest_palindrome_subseq("bbbab"))
print(longest_palindrome_subseq("cbbd"))Prints 4 and 2, the two samples.
When is the program reads dp[l + 1][l], an entry below the diagonal. Nothing writes there, so it still holds its initial 0, the value of an empty range. A string of characters has ranges, which is 500,500 for 1,000 characters, and each entry takes a fixed number of steps. States that are ranges come back in the Interval DP lesson.
Step through the range table
The widget fills the table for bbbab one diagonal at a time, from the single characters to the whole string. This is another order that finishes the shorter ranges first. On its last step it walks back from the top-right entry. Two equal ends go into the palindrome and both move inward, and otherwise the walk moves to the larger of the two neighbouring entries. banana is another word to try: its longest palindromic subsequence is anana.
Deeper read: counting palindromic substrings
A substring is a run of consecutive characters of a string, which is one of the ranges. The next problem asks of every range whether it is a palindrome.
You get a string s. Count its substrings that are palindromes. Equal substrings at different positions count separately.
Constraints
- 1 to 1,000 characters
- Only lowercase English letters
Sample 1 · Input
s = "abc"
Output
3
Sample 2 · Input
s = "aaa"
Output
6
In abc only the three single letters are palindromes. In aaa every range is one: three single letters, two aa and the whole string.
Let pal[l][r] say whether the characters from position to position form a palindrome. They do when s[l] equals s[r] and the characters between them form a palindrome. A range of one or two characters has nothing between its ends, so for it the first condition is enough. The entries are filled in the same order as before, and the answer is the number of true entries.
def count_substrings(s):
n = len(s)
pal = [[False] * n for _ in range(n)]
count = 0
for l in range(n - 1, -1, -1):
for r in range(l, n):
if s[l] == s[r] and (r - l < 2 or pal[l + 1][r - 1]):
pal[l][r] = True
count += 1
return count
print(count_substrings("abc"))
print(count_substrings("aaa"))Prints 3 and 6, the two samples.
The same count can be made without a table. Every palindrome has a centre, which is a character or the gap between two characters, and a string of characters has centres. Growing outward from each centre for as long as the two ends are equal finds the same palindromes, also in time. Manacher's algorithm, in Further reading, brings this down to .
Time and space of these tables
- LCS, edit distance, counting
time and space - One state per pair of prefixes, and at most three candidates each: about a million entries for two strings of 1,000 characters.
- Rebuilding a string
at most steps - Each step of the walk shortens one of the two prefixes. The walk reads the finished table, so every row has to be kept.
- Only the final value
space - A row reads itself and the row above it, so the program can keep two rows and drop the rest. This gives up the walk back.
- Longest palindromic subsequence
time and space - One state per range, and at most two candidates each: 500,500 entries for 1,000 characters.
Common mistakes
Comparing
a[i]withb[j]when and count the characters of the prefixes.- Where it breaks
- For
a = "a"andb = "b"the answer is 0. The Python program stops with anIndexErrorona[1]. The C++ program reads the end-of-string character of both strings, finds the two equal and returns1. - The fix
- The last of the first characters is
a[i - 1], and the last of the first characters isb[j - 1].
Leaving the first row and column of the edit-distance table at 0.
- Where it breaks
edit_distance("ab", "b")returns0, because with the first column at 0 the a is deleted for free. The answer is1.- The fix
- Set
dp[i][0] = ianddp[0][j] = jbefore the loops.
Leaving the first column of the Distinct Subsequences table at 0.
- Where it breaks
num_distinct("rabbbit", "rabbit")returns0instead of3. Every entry is a sum of entries that are all 0.- The fix
- The empty string is spelled in one way inside every prefix of
s, so setways[i][0] = 1.
Filling the palindrome table one row at a time from the top.
- Where it breaks
- For
baathe program returns1. Row 0 readsdp[1][2]before row 1 has been filled and finds 0 there. The answer is2, foraa. - The fix
- Let
lrun fromn - 1down to 0, or fill the ranges in order of length.
Keeping the whole table for two long strings when only the length is asked for.
- Where it breaks
- Two strings of 10,000 characters give entries, which take at least 800 MB as Python lists and 400 MB as C++
intvalues. - The fix
- Keep the current row and the row above it.
Recall Suppose edit distance allowed only insertions and deletions. How does the transition change, and which earlier answer does the distance equal?
A character can no longer be replaced, so when a[i - 1] and b[j - 1] differ the diagonal candidate is gone and the transition is the smaller of dp[i - 1][j] + 1 and dp[i][j - 1] + 1. When they are equal the diagonal entry is still taken at no cost.
The characters that are kept form a common subsequence of the two strings. Every other character of a is deleted and every other character of b is inserted, so the distance is for a longest common subsequence of length , the answer to Delete Operation for Two Strings. For horse and ros one longest common subsequence is os, and the distance is where the usual edit distance is 3.
Further reading
- Jeff Erickson (PDF)Algorithms, Chapter 3: Dynamic programming(opens in a new tab)
Section 3.7 draws a sequence of edits as an alignment of the two strings, builds the edit-distance transition from the alignment's last column, and follows the finished table backwards to recover the edits. Parts of this page adapt this chapter’s text, licensed CC BY 4.0 (creativecommons.org/licenses/by/4.0), with changed wording, examples and code.
- USACO Guide, GoldPaths on Grids(opens in a new tab)
Treats the longest common subsequence as a path through the table: a step right or down skips a character, and each diagonal step on equal characters adds one to the length.
- Antti Laaksonen (PDF)Competitive Programmer’s Handbook, Chapter 7: Dynamic programming(opens in a new tab)
Section 7.5 derives the edit distance from the same three candidates and draws the table and the walk back for LOVE and MOVIE.
- AtCoder Educational DP Contest, problem FF - LCS(opens in a new tab)
Asks for the longest common subsequence itself, for strings of up to 3,000 characters: the table and the walk back of this lesson.
- WikipediaWagner–Fischer algorithm(opens in a new tab)
The edit-distance table under its historical name, with a worked table and the version that stores only the previous and the current column.
- WikipediaHirschberg’s algorithm(opens in a new tab)
Rebuilds the sequence of operations in linear space by splitting the problem in half, for strings too long to keep the whole table.
- cp-algorithmsManacher’s Algorithm(opens in a new tab)
Starts from growing each palindrome outward from its centre and reuses earlier centres to find every palindromic substring in .