DSA for Interviews, From Zero

Part 14 · Lesson 57 · read

DP on Strings

Longest common subsequence, edit distance and the longest palindrome inside a string.

On this page

  1. Two strings, one table
  2. Longest common subsequence
  3. Traced: filling the LCS table
  4. Recovering the actual string
  5. Edit distance
  6. Longest palindromic subsequence
  7. LIS in O(n log n)
  8. Practice questions (7)
  9. Make it stick
  10. What's next

Two strings, one table

Lesson 56 filled two-dimensional tables (tables with rows and columns) for grids and knapsack. Strings work the same way. When a question compares two strings, let one side of the table follow each string. The cell dp[i][j] then answers the question about the first i characters of the first string and the first j characters of the second string. Each cell is worked out from its neighbours: the cell above, the cell to the left, and the cell diagonally up-left. This is just like the grid paths you already know.

Two words matter here. A subsequence keeps the characters in their original order, but it may skip some. "ace" is a subsequence of "abcde". A substring must be one unbroken piece, with no gaps. "bcd" is a substring, but "ace" is not. Read the question twice to see which one it asks about, because the methods are different.

Longest common subsequence

The longest common subsequence (LCS) of two strings is the longest subsequence that appears in both strings. Its characters are in the same order in both, but they do not need to be next to each other. For "abcde" and "ace" it is "ace", with length 3.

Let dp[i][j] be the LCS length of a[0..i) and b[0..j) (the first i characters of a and the first j characters of b). A prefix is the start of a string. Look only at the last character of each prefix:

  • If a[i-1] === b[j-1], the two characters match. It is always safe to use them, so dp[i][j] = dp[i-1][j-1] + 1.
  • If they do not match, at least one of the two last characters is not used. So the answer is the bigger of two choices. You can drop a's last character (dp[i-1][j]), or drop b's last character (dp[i][j-1]).

We add a row and a column of zeros for the empty prefixes. This keeps the index numbers simple. That is why the table has m + 1 rows and n + 1 columns.

JavaScript
// Length of the longest common subsequence of a and b.// dp[i][j] = LCS length of the first i characters of a and the first j characters of b.function lcs(a, b) {  const m = a.length, n = b.length;  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));   // row 0 and column 0 stay 0: an empty prefix has no common part  for (let i = 1; i <= m; i++) {    for (let j = 1; j <= n; j++) {      if (a[i - 1] === b[j - 1]) {        dp[i][j] = dp[i - 1][j - 1] + 1;                  // the two last characters match: extend the diagonal      } else {        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);  // drop a's last character, or drop b's      }    }  }  return dp[m][n];}console.log(lcs("abcde", "ace"));   // 3console.log(lcs("abc", "def"));     // 0console.log(lcs("AGGTAB", "GXTXAYB")); // 4

Time and memory are both O(m × n). Row i only reads row i-1. So you can keep just two rows and use only O(n) memory. The cost is that you can no longer rebuild the string itself.

Traced: filling the LCS table

step 1 / 17
Set up
table of zeros

Each row is the start of "abcde" (0 to 5 characters). Each column is the start of "ace" (0 to 3). Row 0 and column 0 stay 0.

1const m = a.length, n = b.length;▶const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));3for (let i = 1; i <= m; i++) {4  for (let j = 1; j <= n; j++) {5    if (a[i - 1] === b[j - 1]) {6      dp[i][j] = dp[i - 1][j - 1] + 1;7    } else {8      dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);9    }10  }11}12return dp[m][n];
Variables
a"abcde"
b"ace"
dp[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
Console
(nothing printed yet)
A match (line 6) takes the diagonal value and adds 1. A mismatch (line 8) copies the bigger neighbour. The final 3 is the bottom-right corner. · interactive

Recovering the actual string

The table holds lengths, not letters. To get a real LCS, start at the bottom-right corner and follow the choices backwards. If the two characters match, that character is in the answer, and you move diagonally up-left. If they do not match, move to the neighbour with the bigger value. You collect the letters from the end of the string to the start, so reverse them at the end.

JavaScript
// Same table, then walk back from the bottom-right corner to read off one actual LCS.function lcsString(a, b) {  const m = a.length, n = b.length;  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));  for (let i = 1; i <= m; i++) {    for (let j = 1; j <= n; j++) {      dp[i][j] = a[i - 1] === b[j - 1] ? dp[i - 1][j - 1] + 1 : Math.max(dp[i - 1][j], dp[i][j - 1]);    }  }  const letters = [];  let i = m, j = n;  while (i > 0 && j > 0) {    if (a[i - 1] === b[j - 1]) {      letters.push(a[i - 1]);                  // this character is part of the answer      i--; j--;                                // move diagonally    } else if (dp[i - 1][j] >= dp[i][j - 1]) {      i--;                                     // the value came from above: skip a's character    } else {      j--;                                     // the value came from the left: skip b's character    }  }  return letters.reverse().join("");           // we collected the letters from the end, so reverse them}console.log(lcsString("abcde", "ace"));        // aceconsole.log(lcsString("AGGTAB", "GXTXAYB"));   // GTAB
Several answers can tie
Sometimes the cell above and the cell to the left are equal. Then either direction gives a valid longest subsequence, so there can be more than one correct string. Interview questions usually ask only for the length. If they ask for the string, any valid one is normally accepted, but say this out loud.

Edit distance

The edit distance between two words is the smallest number of one-character changes (insert, delete or replace one character) needed to turn the first word into the second. Let dp[i][j] be the cost of turning the first i characters of word1 into the first j characters of word2. Each change matches one move on the table:

  • Replace: swap the last character of word1 for the last character of word2. Then solve the smaller problem: dp[i-1][j-1] + 1 (the cell diagonally up-left).
  • Delete word1's last character: dp[i-1][j] + 1 (the cell above).
  • Insert word2's last character onto word1: dp[i][j-1] + 1 (the cell to the left).
  • If the two last characters are already equal, you need no change. Copy dp[i-1][j-1].

This time the border (the first row and first column) is not zero. Turning i characters into an empty string takes i deletions. Building j characters from nothing takes j insertions.

JavaScript
// Minimum insert / delete / replace operations to turn word1 into word2.// dp[i][j] = edits to turn the first i characters of word1 into the first j characters of word2.function editDistance(word1, word2) {  const m = word1.length, n = word2.length;  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));  for (let i = 0; i <= m; i++) dp[i][0] = i;   // turn i characters into nothing: i deletions  for (let j = 0; j <= n; j++) dp[0][j] = j;   // build j characters from nothing: j insertions  for (let i = 1; i <= m; i++) {    for (let j = 1; j <= n; j++) {      if (word1[i - 1] === word2[j - 1]) {        dp[i][j] = dp[i - 1][j - 1];           // last characters already agree: no operation needed      } else {        dp[i][j] = 1 + Math.min(          dp[i - 1][j - 1],                    // replace word1's last character with word2's          dp[i - 1][j],                        // delete word1's last character          dp[i][j - 1],                        // insert word2's last character at the end        );      }    }  }  return dp[m][n];}console.log(editDistance("horse", "ros"));           // 3console.log(editDistance("intention", "execution")); // 5console.log(editDistance("", "abc"));                // 3
Dry run · "horse" to "ros": the full table (row = prefix of horse, column = prefix of ros)
(empty)ros
0123
h1123
o2212
r3222
s4332
e5443

The last row is the answer row. Its last cell, 3, is the edit distance (horse → rorse → rose → ros: replace h by r, delete r, delete e). The first row (0 1 2 3) and the first column (0 to 5) are the border. They show the cost of building a prefix from nothing, or deleting it completely.

Longest palindromic subsequence

A palindrome reads the same forwards and backwards, like “level”. There are two clear ways to find the longest palindromic subsequence of s.

Way 1: LCS with the reversed string. A subsequence that appears in s and also in reverse(s) reads the same both ways. So the LCS of the two strings is the answer. You have nothing new to learn.

JavaScript
// A palindrome reads the same forwards and backwards, so the longest palindromic// subsequence of s is the longest common subsequence of s and its reverse.function longestPalindromeSubseq(s) {  const t = s.split("").reverse().join("");  const n = s.length;  const dp = Array.from({ length: n + 1 }, () => new Array(n + 1).fill(0));  for (let i = 1; i <= n; i++) {    for (let j = 1; j <= n; j++) {      dp[i][j] = s[i - 1] === t[j - 1] ? dp[i - 1][j - 1] + 1 : Math.max(dp[i - 1][j], dp[i][j - 1]);    }  }  return dp[n][n];}console.log(longestPalindromeSubseq("bbbab"));  // 4   ("bbbb")console.log(longestPalindromeSubseq("cbbd"));   // 2   ("bb")

Way 2: interval DP. Interval DP is DP where the state is a slice (interval) of one string or array. An interval is a slice of the string from position i to position j. Let dp[i][j] be the answer for the slice s[i..j]. If the two ends match, they wrap around the best palindrome of the inside, and we add 2. If they do not match, drop one end. We must fill the table from short slices to long slices. The code does this by looping bottom-up: dp[i] needs dp[i+1], so i runs downwards.

JavaScript
// Interval DP: dp[i][j] = longest palindromic subsequence inside s[i..j] (both ends included).function longestPalindromeSubseq(s) {  const n = s.length;  const dp = Array.from({ length: n }, () => new Array(n).fill(0));  for (let i = n - 1; i >= 0; i--) {           // go from the bottom row up: dp[i] needs dp[i + 1]    dp[i][i] = 1;                              // a single character is a palindrome of length 1    for (let j = i + 1; j < n; j++) {      if (s[i] === s[j]) {        dp[i][j] = dp[i + 1][j - 1] + 2;       // matching ends wrap whatever is best in between      } else {        dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);   // drop the left end, or drop the right end      }    }  }  return dp[0][n - 1];}console.log(longestPalindromeSubseq("bbbab"));  // 4console.log(longestPalindromeSubseq("cbbd"));   // 2console.log(longestPalindromeSubseq("a"));      // 1

Both take O(n²) time. Interval DP is worth knowing. Many problems that ask for "the best answer for the slice from i to j" look like this.

LIS in O(n log n)

Lesson 55 solved the longest increasing subsequence (LIS) with an O(n²) DP. “Strictly increasing” means every number is bigger than the one before it. Here is that slower version again, so we can compare:

JavaScript
// O(n^2): best[i] = length of the longest increasing subsequence that ENDS at index i.function lisQuadratic(nums) {  const best = new Array(nums.length).fill(1);  let answer = 0;  for (let i = 0; i < nums.length; i++) {    for (let j = 0; j < i; j++) {      if (nums[j] < nums[i]) best[i] = Math.max(best[i], best[j] + 1);    }    answer = Math.max(answer, best[i]);  }  return answer;}console.log(lisQuadratic([10, 9, 2, 5, 3, 7, 101, 18])); // 4

The faster method keeps an array called tails. The value tails[k] is the smallest possible last value of any increasing subsequence with length k + 1 that we have seen so far. A smaller last value is better, because it is easier to add to. Two facts follow. First, tails is always sorted from small to big, so we can use binary search (a way to find a spot in a sorted list by checking the middle and discarding the half that cannot contain it). Second, each new number x has only two cases:

  • x is bigger than every tail. It makes the longest subsequence one longer, so add it at the end.
  • Otherwise, find the first tail that is >= x (use binary search) and replace it with x. A subsequence of that length can now end on a smaller value.
JavaScript
// O(n log n). tails[k] = the smallest possible LAST value of an increasing subsequence of length k + 1.// tails is always sorted, so we can binary search it.function lengthOfLIS(nums) {  const tails = [];  for (const x of nums) {    let lo = 0, hi = tails.length;             // find the first index whose value is >= x    while (lo < hi) {      const mid = (lo + hi) >> 1;      if (tails[mid] < x) lo = mid + 1;      else hi = mid;    }    tails[lo] = x;                             // lo === tails.length means "extend by one"; otherwise "lower an existing tail"  }  return tails.length;}console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])); // 4console.log(lengthOfLIS([0, 1, 0, 3, 2, 3]));            // 4console.log(lengthOfLIS([7, 7, 7, 7]));                  // 1
Dry run · nums = [10, 9, 2, 5, 3, 7, 101, 18]
xtails after itWhat happened
10[10]tails was empty, so start a subsequence of length 1
9[9]9 replaces 10. A smaller last value for length 1 is always better
2[2]2 replaces 9, for the same reason
5[2, 5]5 is bigger than every tail, so add it. Length is now 2
3[2, 3]3 replaces 5. Now length 2 can end at 3
7[2, 3, 7]add it. Length is now 3
101[2, 3, 7, 101]add it. Length is now 4
18[2, 3, 7, 18]18 replaces 101. The answer is the length of tails, which is 4

The length of tails is the answer. Binary search costs O(log n) for each number, so the total is O(n log n). We use >= (find the first tail that is not smaller than x). The subsequence must be strictly increasing, so an equal value must replace a tail and must not extend it.

tails is NOT the subsequence
Only its length is always correct. The values in tails may come from different positions. They do not have to form a subsequence of the input. This small example shows it:
JavaScript
// Watch tails change. Note that it is NOT the subsequence itself.function showTails(nums) {  const tails = [];  for (const x of nums) {    let lo = 0, hi = tails.length;    while (lo < hi) {      const mid = (lo + hi) >> 1;      if (tails[mid] < x) lo = mid + 1; else hi = mid;    }    tails[lo] = x;    console.log(x, "->", [...tails]);  }}showTails([4, 5, 1]);// 4 -> [ 4 ]// 5 -> [ 4, 5 ]// 1 -> [ 1, 5 ]      but 1, 5 is not a subsequence of [4, 5, 1]: the 5 comes BEFORE the 1

To rebuild the real subsequence, you would also remember, for each element, which earlier index it extended. Then you walk back from the last tail. Questions almost always ask only for the length.

Practice questions

For each question, say out loud what dp[i][j] (or dp[i]) means before you write any code.

Q1Longest common subsequenceMedium

Given two strings text1 and text2, return the length of their longest common subsequence, or 0 if there is none. A subsequence keeps the original order, but it may skip characters.

Example 1
Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace".
Example 2
Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The strings are identical.
Example 3
Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: No character is shared.
Stuck? Open one hint at a time
Hint 1
Let dp[i][j] be the answer for the first i characters of one string and the first j characters of the other.
Hint 2
Look at the last characters of the two prefixes (the starts of the strings). What if they are equal? What if they are different?
Hint 3
Equal: 1 + the answer without both characters. Different: the bigger answer from dropping one character or the other.
Show all 3 solutions with explanations
Approach 1Top-down recursion with memoisation
The idea

Define solve(i, j) for the first i and first j characters. Memoisation (memoization) means saving each answer after you work it out, so you never work it out twice. Save the answer for each pair. Without the saved answers, the recursion splits in two at every mismatch. That is exponential, which means the work doubles again and again.

JavaScript
function longestCommonSubsequence(text1, text2) {  const memo = new Map();  function solve(i, j) {    if (i === 0 || j === 0) return 0;    const key = i * 1001 + j;    if (memo.has(key)) return memo.get(key);    const result = text1[i - 1] === text2[j - 1]      ? solve(i - 1, j - 1) + 1      : Math.max(solve(i - 1, j), solve(i, j - 1));    memo.set(key, result);    return result;  }  return solve(text1.length, text2.length);}console.log(longestCommonSubsequence("abcde", "ace")); // 3console.log(longestCommonSubsequence("abc", "abc"));   // 3console.log(longestCommonSubsequence("abc", "def"));   // 0
How it works

There are m × n different pairs and each is worked out once, so O(m × n) time and memory. The recursion can go m + n calls deep. That is fine for the usual limit of 1000 characters each.

Approach 2Bottom-up table
The idea

Fill an (m+1) × (n+1) table row by row. Use zeros for the empty prefixes.

JavaScript
function longestCommonSubsequence(text1, text2) {  const m = text1.length, n = text2.length;  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));  for (let i = 1; i <= m; i++) {    for (let j = 1; j <= n; j++) {      dp[i][j] = text1[i - 1] === text2[j - 1]        ? dp[i - 1][j - 1] + 1        : Math.max(dp[i - 1][j], dp[i][j - 1]);    }  }  return dp[m][n];}console.log(longestCommonSubsequence("abcde", "ace")); // 3console.log(longestCommonSubsequence("abc", "abc"));   // 3console.log(longestCommonSubsequence("abc", "def"));   // 0
How it works

The time is the same O(m × n), with no recursion. If you are asked for the string itself, you walk back through this table.

Approach 3Two rows only
The idea

Row i reads only row i-1 and the cell to its own left. So keep two rows, prev (the old row) and curr (the new row), and swap them.

JavaScript
function longestCommonSubsequence(text1, text2) {  const n = text2.length;  let prev = new Array(n + 1).fill(0);  for (let i = 1; i <= text1.length; i++) {    const curr = new Array(n + 1).fill(0);    for (let j = 1; j <= n; j++) {      curr[j] = text1[i - 1] === text2[j - 1]        ? prev[j - 1] + 1        : Math.max(prev[j], curr[j - 1]);    }    prev = curr;  }  return prev[n];}console.log(longestCommonSubsequence("abcde", "ace")); // 3console.log(longestCommonSubsequence("abc", "abc"));   // 3console.log(longestCommonSubsequence("abc", "def"));   // 0
How it works

Time is still O(m × n), but memory drops to O(n). To save the most, make the second string the shorter one.

Which approach should you use?

Start with the table. It is the version everybody expects, and the other two are small changes to it. Mention the two-row trick if memory comes up. (LeetCode 1143.)

Q2Edit distanceMedium

Given two strings word1 and word2, return the smallest number of operations to turn word1 into word2. The allowed operations are: insert a character, delete a character, and replace a character.

Example 1
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: horse → rorse (replace h with r) → rose (delete r) → ros (delete e).
Example 2
Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: Delete t, replace i with e, replace n with x, replace n with c, insert u.
Stuck? Open one hint at a time
Hint 1
dp[i][j] = the fewest edits to turn the first i characters of word1 into the first j characters of word2.
Hint 2
If the last characters match, they cost nothing. If not, you have three choices: replace, delete or insert.
Hint 3
What does it cost to turn an empty string into a longer one, or a longer one into an empty string? Those are your border values.
Show all 3 solutions with explanations
Approach 1Top-down recursion with memoisation
The idea

Compare the last characters of the two prefixes. If they are equal, drop both for free. If not, try replace, delete and insert, and take 1 + the cheapest. Save every answer (i, j) so you never repeat work.

JavaScript
function minDistance(word1, word2) {  const memo = new Map();  function solve(i, j) {    if (i === 0) return j;                  // build j characters from nothing: j insertions    if (j === 0) return i;                  // remove i characters: i deletions    const key = i * 1001 + j;    if (memo.has(key)) return memo.get(key);    let result;    if (word1[i - 1] === word2[j - 1]) {      result = solve(i - 1, j - 1);    } else {      result = 1 + Math.min(solve(i - 1, j - 1), solve(i - 1, j), solve(i, j - 1));    }    memo.set(key, result);    return result;  }  return solve(word1.length, word2.length);}console.log(minDistance("horse", "ros"));           // 3console.log(minDistance("intention", "execution")); // 5console.log(minDistance("", "a"));                  // 1
How it works

Without the saved answers, each mismatch splits three ways. That is exponential. With them, there are m × n states and each takes O(1) work.

Approach 2Bottom-up table
The idea

Fill the border first: 0..m down the first column and 0..n along the first row. Then fill each cell from its left, upper and diagonal neighbours.

JavaScript
function minDistance(word1, word2) {  const m = word1.length, n = word2.length;  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));  for (let i = 0; i <= m; i++) dp[i][0] = i;  for (let j = 0; j <= n; j++) dp[0][j] = j;  for (let i = 1; i <= m; i++) {    for (let j = 1; j <= n; j++) {      if (word1[i - 1] === word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];      else dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]);    }  }  return dp[m][n];}console.log(minDistance("horse", "ros"));           // 3console.log(minDistance("intention", "execution")); // 5console.log(minDistance("", "a"));                  // 1
How it works

O(m × n) time and memory. The diagonal move is replace. The move from above is delete. The move from the left is insert.

Approach 3Two rows
The idea

Each row needs only the row above, so keep two arrays. The first cell of row i is i (all deletions).

JavaScript
function minDistance(word1, word2) {  const n = word2.length;  let prev = Array.from({ length: n + 1 }, (_, j) => j);  for (let i = 1; i <= word1.length; i++) {    const curr = new Array(n + 1);    curr[0] = i;    for (let j = 1; j <= n; j++) {      curr[j] = word1[i - 1] === word2[j - 1]        ? prev[j - 1]        : 1 + Math.min(prev[j - 1], prev[j], curr[j - 1]);    }    prev = curr;  }  return prev[n];}console.log(minDistance("horse", "ros"));           // 3console.log(minDistance("intention", "execution")); // 5console.log(minDistance("", "a"));                  // 1
How it works

The time is the same O(m × n), and the memory is O(n).

Which approach should you use?

The full table is the easiest to explain. You can point at the three neighbours and name the change each one stands for. Offer the two-row version as the way to save memory. (LeetCode 72.)

Q3Longest palindromic subsequenceMedium

Given a string s, return the length of its longest palindromic subsequence (the characters stay in order, and gaps are allowed).

Example 1
Input: s = "bbbab"
Output: 4
Explanation: One longest palindromic subsequence is "bbbb".
Example 2
Input: s = "cbbd"
Output: 2
Explanation: One longest palindromic subsequence is "bb".
Stuck? Open one hint at a time
Hint 1
A palindrome is the same as its own reverse. Which problem you know compares one string with another string?
Hint 2
Or look at the slice s[i..j]. What do the two end characters tell you if they are equal? What if they are different?
Show all 2 solutions with explanations
Approach 1LCS of the string and its reverse
The idea

A subsequence of s that is also a subsequence of reverse(s) reads the same in both directions. So run the LCS table on the string and its reverse.

JavaScript
function longestPalindromeSubseq(s) {  const t = s.split("").reverse().join("");  const n = s.length;  const dp = Array.from({ length: n + 1 }, () => new Array(n + 1).fill(0));  for (let i = 1; i <= n; i++) {    for (let j = 1; j <= n; j++) {      dp[i][j] = s[i - 1] === t[j - 1]        ? dp[i - 1][j - 1] + 1        : Math.max(dp[i - 1][j], dp[i][j - 1]);    }  }  return dp[n][n];}console.log(longestPalindromeSubseq("bbbab")); // 4console.log(longestPalindromeSubseq("cbbd"));  // 2console.log(longestPalindromeSubseq("a"));     // 1
How it works

O(n²) time and memory. It reuses the last problem and is hard to get wrong. That makes it a good first answer when you feel nervous.

Approach 2Interval DP
The idea

dp[i][j] is the answer for the slice s[i..j]. If the ends are equal, add 2 to the answer for the inside. If they are different, drop one end. Loop i downwards, so dp[i+1] is ready when you need it.

JavaScript
function longestPalindromeSubseq(s) {  const n = s.length;  const dp = Array.from({ length: n }, () => new Array(n).fill(0));  for (let i = n - 1; i >= 0; i--) {    dp[i][i] = 1;    for (let j = i + 1; j < n; j++) {      if (s[i] === s[j]) dp[i][j] = dp[i + 1][j - 1] + 2;      else dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);    }  }  return dp[0][n - 1];}console.log(longestPalindromeSubseq("bbbab")); // 4console.log(longestPalindromeSubseq("cbbd"));  // 2console.log(longestPalindromeSubseq("a"));     // 1
How it works

When j = i + 1 and the characters match, dp[i+1][j-1] is dp[i+1][i]. That is an empty slice, and it is still 0 because the table started full of zeros. O(n²) time and memory.

Which approach should you use?

Both take O(n²). The reverse trick is quicker to write. The interval version shows that you know a pattern that appears in many other problems. (LeetCode 516.)

Q4Longest increasing subsequence in O(n log n)Medium

Given an integer array nums, return the length of the longest strictly increasing subsequence (each number is bigger than the one before). Aim for O(n log n).

Example 1
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: One longest increasing subsequence is [2, 3, 7, 18].
Example 2
Input: nums = [0,1,0,3,2,3]
Output: 4
Explanation: For example [0, 1, 2, 3].
Example 3
Input: nums = [7,7,7,7]
Output: 1
Explanation: The subsequence must be strictly increasing, so equal values do not count.
Stuck? Open one hint at a time
Hint 1
The O(n²) DP asks, for each element, which earlier smaller element to build on. Can you make that choice faster?
Hint 2
Keep tails[k]: the smallest last value of any increasing subsequence with length k + 1. Is that array sorted?
Hint 3
For a new number, use binary search to find the first tail that is >= it, and replace that slot. If there is none, add the number at the end.
Show all 2 solutions with explanations
Approach 1DP in O(n²)
The idea

best[i] is the length of the longest increasing subsequence that ends at index i. It is 1 plus the best value among all earlier smaller numbers.

JavaScript
function lengthOfLIS(nums) {  const best = new Array(nums.length).fill(1);  let answer = 0;  for (let i = 0; i < nums.length; i++) {    for (let j = 0; j < i; j++) {      if (nums[j] < nums[i]) best[i] = Math.max(best[i], best[j] + 1);    }    answer = Math.max(answer, best[i]);  }  return answer;}console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])); // 4console.log(lengthOfLIS([0, 1, 0, 3, 2, 3]));            // 4console.log(lengthOfLIS([7, 7, 7, 7]));                  // 1
How it works

Two loops inside each other over n elements give O(n²) time and O(n) memory. This is fine for n up to a couple of thousand, but too slow for more.

Approach 2Tails array with binary search
The idea

Keep a sorted tails array. For each number, use binary search (check the middle again and again) to find the first tail that is at least as large, and replace it. If there is none, add the number at the end. The final length is the answer.

JavaScript
function lengthOfLIS(nums) {  const tails = [];  for (const x of nums) {    let lo = 0, hi = tails.length;    while (lo < hi) {      const mid = (lo + hi) >> 1;      if (tails[mid] < x) lo = mid + 1;      else hi = mid;    }    tails[lo] = x;  }  return tails.length;}console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])); // 4console.log(lengthOfLIS([0, 1, 0, 3, 2, 3]));            // 4console.log(lengthOfLIS([7, 7, 7, 7]));                  // 1
How it works

Replacing a tail never changes how long the subsequences are. It only makes them easier to extend later. Each number costs one O(log n) binary search, so the total is O(n log n) time and O(n) memory. Remember that tails is not itself a valid subsequence. Only its length is the answer.

Which approach should you use?

If you are unsure, give the O(n²) DP first. Then offer the tails method as the faster version. If the interviewer asks for the subsequence itself, the O(n²) DP is simpler to explain. It remembers which earlier element each one came from. (LeetCode 300.)

Q5Delete operation for two stringsMedium

Given two strings word1 and word2, return the smallest number of one-character deletions (from either string) needed to make the two strings equal.

Example 1
Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: Delete "s" from "sea" and "t" from "eat". Both become "ea".
Example 2
Input: word1 = "leetcode", word2 = "etco"
Output: 4
Explanation: The common subsequence "etco" has length 4. So delete the other 4 characters of "leetcode" and nothing from "etco".
Stuck? Open one hint at a time
Hint 1
Only deletions are allowed. What is left in each string when you finish? It must be the same string, and it is a subsequence of both strings.
Hint 2
To delete as little as possible, keep as much as possible. Which problem have you seen like that?
Show all 2 solutions with explanations
Approach 1Through the LCS length
The idea

Whatever is left must be a common subsequence. Keep the longest one and delete everything else from both strings: m + n - 2 × LCS.

JavaScript
function minDistance(word1, word2) {  const m = word1.length, n = word2.length;  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));  for (let i = 1; i <= m; i++) {    for (let j = 1; j <= n; j++) {      dp[i][j] = word1[i - 1] === word2[j - 1]        ? dp[i - 1][j - 1] + 1        : Math.max(dp[i - 1][j], dp[i][j - 1]);    }  }  return m + n - 2 * dp[m][n];}console.log(minDistance("sea", "eat"));          // 2console.log(minDistance("leetcode", "etco"));    // 4console.log(minDistance("abc", "abc"));          // 0
How it works

O(m × n) time and memory. Each deleted character is in one of the strings but not in the kept subsequence. So the total number of deletions is (m - L) + (n - L), where L is the LCS length.

Approach 2Direct DP on deletions
The idea

The table has the same shape as edit distance, but only deletions are allowed. A match is free. A mismatch costs one deletion from either side. The borders are i and j.

JavaScript
function minDistance(word1, word2) {  const m = word1.length, n = word2.length;  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));  for (let i = 0; i <= m; i++) dp[i][0] = i;  for (let j = 0; j <= n; j++) dp[0][j] = j;  for (let i = 1; i <= m; i++) {    for (let j = 1; j <= n; j++) {      if (word1[i - 1] === word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];      else dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1]);    }  }  return dp[m][n];}console.log(minDistance("sea", "eat"));          // 2console.log(minDistance("leetcode", "etco"));    // 4console.log(minDistance("abc", "abc"));          // 0
How it works

This is edit distance without the replace move. It gives the same answers as the LCS formula, in the same O(m × n) time.

Which approach should you use?

The LCS formula is one line once you see it. Seeing the link is the point of the question. The direct DP is a good back-up if you do not see the link. (LeetCode 583.)

Q6Longest palindromic substringMedium

Given a string s, return its longest palindromic substring (one unbroken piece). If several have the same length, any of them is accepted.

Example 1
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a correct answer.
Example 2
Input: s = "cbbd"
Output: "bb"
Explanation: The longest palindrome is the even-length piece in the middle.
Stuck? Open one hint at a time
Hint 1
This time the characters must be together with no gaps (contiguous). Every palindrome has a centre.
Hint 2
From each possible centre, grow outwards while the two sides match. How many centres are there? Remember even-length palindromes too.
Hint 3
Or let dp[i][j] = "is s[i..j] a palindrome?" The answer depends on the two ends and on dp[i+1][j-1].
Show all 3 solutions with explanations
Approach 1Brute force: check every substring
The idea

Try every pair of start and end positions. Check if each piece is a palindrome. Keep the longest one.

JavaScript
function longestPalindrome(s) {  let best = "";  for (let i = 0; i < s.length; i++) {    for (let j = i; j < s.length; j++) {      if (j - i + 1 <= best.length) continue;      let l = i, r = j, ok = true;      while (l < r) {        if (s[l++] !== s[r--]) { ok = false; break; }      }      if (ok) best = s.slice(i, j + 1);    }  }  return best;}console.log(longestPalindrome("babad")); // babconsole.log(longestPalindrome("cbbd"));  // bb
How it works

There are O(n²) substrings and each check costs O(n), so the total is O(n³). Mention it to show you have a starting point, then improve it.

Approach 2Expand around each centre
The idea

A palindrome is a mirror around its centre. The centre is one character for odd length, or the gap between two characters for even length. That gives 2n - 1 centres. Grow outwards from each centre while both sides match.

JavaScript
function longestPalindrome(s) {  let start = 0, bestLen = 0;  function expand(l, r) {    while (l >= 0 && r < s.length && s[l] === s[r]) { l--; r++; }    const len = r - l - 1;                    // the loop overshot by one on each side    if (len > bestLen) { bestLen = len; start = l + 1; }  }  for (let i = 0; i < s.length; i++) {    expand(i, i);                             // odd length, centre at i    expand(i, i + 1);                         // even length, centre between i and i + 1  }  return s.slice(start, start + bestLen);}console.log(longestPalindrome("babad")); // babconsole.log(longestPalindrome("cbbd"));  // bbconsole.log(longestPalindrome("a"));     // a
How it works

Each expansion takes O(n) in the worst case (a string like "aaaa…"), and there are 2n - 1 of them. So the time is O(n²) and the extra memory is O(1).

Approach 3DP table
The idea

isPal[i][j] is true when s[i] === s[j] and the inside piece s[i+1..j-1] is a palindrome (or has at most one character). Fill the table from the bottom row upwards.

JavaScript
function longestPalindrome(s) {  const n = s.length;  const isPal = Array.from({ length: n }, () => new Array(n).fill(false));  let start = 0, bestLen = 1;  for (let i = n - 1; i >= 0; i--) {    for (let j = i; j < n; j++) {      if (s[i] === s[j] && (j - i < 2 || isPal[i + 1][j - 1])) {        isPal[i][j] = true;        if (j - i + 1 > bestLen) { bestLen = j - i + 1; start = i; }      }    }  }  return s.slice(start, start + bestLen);}console.log(longestPalindrome("babad")); // aba   ("bab" is equally valid)console.log(longestPalindrome("cbbd"));  // bbconsole.log(longestPalindrome("a"));     // a
How it works

O(n²) time and O(n²) memory. An interviewer may expect this DP. But it uses more memory than expanding around centres, for the same time.

Which approach should you use?

Prefer expanding around centres. It takes O(n²) time, O(1) memory, and the code is short. Know the DP version too, because the idea works for other problems. (Manacher's algorithm reaches O(n), but interviewers rarely expect it.) (LeetCode 5.)

Q7Palindromic substringsMedium

Given a string s, return the number of palindromic substrings in it. Substrings with different start or end positions count separately, even if the text is the same.

Example 1
Input: s = "abc"
Output: 3
Explanation: Only the single letters "a", "b", "c" are palindromes.
Example 2
Input: s = "aaa"
Output: 6
Explanation: "a" three times, "aa" twice and "aaa" once. Substrings at different positions count separately.
Stuck? Open one hint at a time
Hint 1
Use the same centres as in the longest palindromic substring. This time, count every step of growing outwards that still matches.
Hint 2
Each step that still matches is one more palindrome.
Show all 2 solutions with explanations
Approach 1Expand around each centre
The idea

For every odd-length and even-length centre, grow outwards. Add one to the count each time the two sides match.

JavaScript
function countSubstrings(s) {  let count = 0;  function expand(l, r) {    while (l >= 0 && r < s.length && s[l] === s[r]) {      count++;                                // s[l..r] is a palindrome      l--; r++;    }  }  for (let i = 0; i < s.length; i++) {    expand(i, i);    expand(i, i + 1);  }  return count;}console.log(countSubstrings("abc")); // 3console.log(countSubstrings("aaa")); // 6
How it works

Every palindromic substring has exactly one centre, so each one is counted exactly once. O(n²) time, O(1) memory.

Approach 2DP table
The idea

Use the same isPal[i][j] table as before. Count the cells that are true.

JavaScript
function countSubstrings(s) {  const n = s.length;  const isPal = Array.from({ length: n }, () => new Array(n).fill(false));  let count = 0;  for (let i = n - 1; i >= 0; i--) {    for (let j = i; j < n; j++) {      if (s[i] === s[j] && (j - i < 2 || isPal[i + 1][j - 1])) {        isPal[i][j] = true;        count++;      }    }  }  return count;}console.log(countSubstrings("abc")); // 3console.log(countSubstrings("aaa")); // 6
How it works

O(n²) time and O(n²) memory. Each cell decides one substring.

Which approach should you use?

Expanding around centres uses less memory and is shorter. This question is the counting twin of LeetCode 5, so if you solve one you can solve the other. (LeetCode 647.)

Make it stick

Make it stick — close this page, then
  1. Write the LCS rule from memory. Include what the border row and column hold.
  2. Walk back through an LCS table to get the string. Say why you reverse it at the end.
  3. Match insert, delete and replace to the three neighbouring cells in edit distance.
  4. Explain two ways to find the longest palindromic subsequence.
  5. Explain what tails[k] means in the O(n log n) LIS. Say why tails is not the subsequence.
  6. Say how a subsequence is different from a substring.

Revisit schedule: solve two of the questions again tomorrow, again in 3 days, and once more in a week — without looking at the answers. Each time it will feel easier. That is the memory forming.

What's next

That finishes dynamic programming. Lesson 58 starts the last part with two small toolkits that interviews often use. One is the trie, a tree made for working with the starts of words (prefixes). The other is bit manipulation, which means small tricks that work on the binary form of numbers (the 0s and 1s a computer uses). After that, Lesson 59 shows how to run the interview itself.

Practise on LeetCode

Real interview problems that use exactly what this lesson teaches. Solve them in JavaScript after the practice questions above.

Published by Jainik · Last updated · How these lessons are made

Keep learning

Part of the study guide

Related series