Longest common subsequence (LCS) is a classic problem of dynamic programming. The problem is to find out the longest subsequence which presents in the two given sequences. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous.

The solution of LCS is delicate, and the idea can be applied to many other problems. I will walk through these problems in this post.

## I. Solution of LCS

The key is to break down the problem into a collection of simpler subproblems.

If we need to return the subsequence, we can use a matrix to record the path we take in the if/else above and then recover the subsequence according to it.

## II. Applying the idea of LCS

### i. Longest Common Substring

It is a bit different from Longest Common Subsequence. Substring requires to be contiguous. But the solution is similar. Note that this is not a problem of dp, the answer is not mark[s1.length()][s2.length()], but the max value in the matrix.

A similar problem on leetcode: 718. Maximum Length of Repeated Subarray.

### ii. Interleaving String

97. Interleaving String: given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

We can directly apply the idea of LCS to this problem. Just be aware of the index.

## III. Matching

### i. Regular expression matching

10. Regular Expression Matching: decide if the pattern p matches the string s. ‘.’ matches any single character; ‘*’ matches zero or more of the preceding element.

### ii. Wilcard matching

44. Wildcard Matching: decide if the pattern p matches the string s. ‘?’ matches any single character; ‘*’ matches any sequence of characters (including the empty sequance).

## IV. Edit distance

### i. Delete distance

583. Delete Operation for Two Strings: given two words word1 and word2, find the minimum number of steps required to make word1 and word2 the same, where in each step you can delete one character in either string.

The idea is to find the LCS and remove the rest characters. Or we can directly apply the idea of LCS to this problem.

### ii. Edit distance

72. Edit Distance: given two words word1 and word2, find the minimum number of steps required to make word1 and word2 the same, where in each step you can insert/delete/edit one character in either string.

The solution is to apply the idea of LCS to this problem. As the insert operation is the same as the delete operation, we can just use either one.

## V. Palindrome

### i. Longest Palindromic Subsequence

516. Longest Palindromic Subsequence: find the longest palindromic subsequence’s length in the given string s.

One solution is to reverse string s and find the LCS of s and the reversed string. Time complexity is O(s.length() * s.length()).

Another solution is to apply the idea of LCS.

Time complexity is: O(s.length() * s.length()).

### ii. Longest Palindromic Substring

5. Longest Palindromic Substring: find the longest palindromic substring in the given string s.

A straight-forward solution is to traverse the array and check if an element is the center of a palindrome.

Time complexity: O(s.length() * s.length()).

Another solution is to apply the idea of LCS.

Time complexity is: O(s.length() * s.length()).

Note that the trick that reverses the string and then finds the longest common substring does not work here. This is a counterexample: “abcdkecba”.