Longest Common Subsequence

Problem Statement

Given two sequences, find the length of the longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous.

Solution Approach

We'll use dynamic programming to solve this efficiently. We'll create a 2D table where cell [i][j] represents the length of LCS of the first i characters of str1 and first j characters of str2. We'll build this table step by step, comparing characters and using previously computed results.

Interactive Visualization

String 1:

String 2:

		A	E	D	F	H	R

Step: 0 of 48

Explanation:

Final Result

The length of the Longest Common Subsequence is: