Longest Common Subsequence in Java: Explanation & Practice

Find length of longest common subsequence of two strings

Problem summary

Given two strings, find the length of their longest common subsequence. A subsequence doesn't need to be contiguous.

Starter code

public class Main {
    public static void main(String[] args) {
        String s1 = "abcde";
        String s2 = "ace";
        
        // dp[i][j] = LCS of s1[0..i-1] and s2[0..j-1]
        // If match: 1 + dp[i-1][j-1]
        // Else: max(dp[i-1][j], dp[i][j-1])
        // Print: LCS length: 3
    }
}

Expected output and test cases

abcde, ace → ace
```
LCS length: 3
```
abc, abc → abc
```
LCS length: 3
```
abc, def → empty
```
LCS length: 0
```

Hints

Use 2D DP: dp[i][j] = LCS of first i chars of s1 and first j chars of s2
If s1[i-1] == s2[j-1]: we found a match, add 1 to dp[i-1][j-1]
If no match: take max of skipping char from either string
Base case: dp[0][j] = dp[i][0] = 0

Related Data Structures & Algorithms exercises

Practice all Data Structures & Algorithms exercises · Run this idea in the Java compiler