Longest Common Subsequence: the idea to remember.

The core insight

If final characters match, extend the previous diagonal. Otherwise discard one final character and keep the larger result.

Why it works

A common subsequence either uses the matching pair or can be represented after excluding a nonmatching endpoint. The prefix table covers both choices.

The mistake to avoid

Subsequence permits gaps; substring does not. Keep an extra empty prefix row and column.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

int longestCommonSubsequence(String a, String b) {
    int[][] dp = new int[a.length() + 1][b.length() + 1];
    for (int i = 1; i <= a.length(); i++) {
        for (int j = 1; j <= b.length(); j++) {
            dp[i][j] = a.charAt(i - 1) == b.charAt(j - 1)
                ? 1 + dp[i - 1][j - 1] : Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[a.length()][b.length()];
}

Make the next connection