🔗

LCS Puzzle Match

Intermediate

Find the longest common subsequence between two strings by matching characters in order. Learn dynamic programming through interactive gameplay.

20-25 min
Level 1
Score: 0

String A:

String B:

🎯 Problem Statement

Given two strings, find the longest subsequence that appears in both strings in the same order. A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

💡 Key Concepts

Order Preservation

Characters must appear in the same relative order in both strings, but they don't need to be consecutive.

2D Dynamic Programming

Use a 2D table where dp[i][j] represents the LCS length of first i characters of string1 and first j characters of string2.

📋 Algorithm Pseudo Code

function longestCommonSubsequence(str1, str2):
    m = length(str1)
    n = length(str2)
    
    // Initialize 2D DP table
    dp = array[m+1][n+1] filled with 0
    
    // Fill the DP table
    for i from 1 to m:
        for j from 1 to n:
            if str1[i-1] == str2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    // Reconstruct the LCS
    lcs = ""
    i = m, j = n
    while i > 0 and j > 0:
        if str1[i-1] == str2[j-1]:
            lcs = str1[i-1] + lcs
            i = i - 1
            j = j - 1
        elif dp[i-1][j] > dp[i][j-1]:
            i = i - 1
        else:
            j = j - 1
    
    return lcs

🔍 Step-by-Step Example

Input: str1 = "ABCDEF", str2 = "AEBDF"

DP Table Construction: Fill table using the recurrence relation

Matching: When characters match, add 1 to diagonal value

Result: LCS = "ABDF" (length 4)

📊 DP Table Visualization

Example: "ABCDEF" vs "AEBDF"
A
E
B
D
F
A
1
1
1
1
1
1
1
B
1
1
2
2
2
2
2
C
1
1
2
2
2
2
2
D
1
1
2
3
3
3
3
E
1
1
2
3
3
3
3
F
1
1
2
3
4
4
4
Green cells show where characters match and LCS length increases

⏱️ Complexity Analysis

Time Complexity

O(m × n) where m and n are the lengths of the two strings

Space Complexity

O(m × n) for the DP table

🌍 Real-world Applications

🧬DNA sequence analysis
📝Plagiarism detection
🔍File diff algorithms
📊Data comparison
Progress1 / 5
Algorithm:LCS
🎯 How to Play

1. Click on a character in String A

2. Click on the same character in String B

3. Characters must be matched in order

4. Find the longest common subsequence

5. Complete all levels to win!