Longest Common Subsequence

Category

DP - Multidimensional

Checkbox

Difficulty

Medium

Index

Key Ideas

The key idea to solve this problem is to use dynamic programming to find the longest common subsequence between two given strings.

Problem Number

1143

Problem Summary

The Longest Common Subsequence problem, with problem number 1143 on LeetCode, is a medium difficulty problem categorized under DP - Multidimensional. The goal is to find the length of the longest common subsequence between two given strings. One key pitfall to watch out for is mistakenly assuming that the longest common subsequence must be contiguous within the strings, when it can actually be non-contiguous.

Solution Summary

The best solution to solve the Longest Common Subsequence problem is to use dynamic programming. We can create a 2D array to store the lengths of the common subsequences between the two given strings. We initialize the first row and column with zeros. Then, we iterate through the characters of both strings, comparing them. If the characters are the same, we increment the value in the cell diagonally above and to the left by 1. Otherwise, we take the maximum value from the cell above or the cell to the left. Finally, the value in the bottom-right cell of the matrix represents the length of the longest common subsequence.