Subsequence Problems

Subsequence DP compares two strings (or one string against itself) by building a 2D table over prefixes. This lesson covers the longest common subsequence (LCS, LeetCode 1143), longest palindromic subsequence (516), related variants, and full solutions in C, Java, and Python with trace tables.

Overview

A subsequence keeps characters in order but may skip any number of them. Subsequence DP typically uses:

State:  dp[i][j] = answer for first i chars of A and first j chars of B
Base:   dp[0][*] = dp[*][0] = 0  (empty prefix)

Match:   dp[i][j] = dp[i-1][j-1] + 1        (or +2 for palindrome pairs)
Mismatch: dp[i][j] = max(dp[i-1][j], dp[i][j-1])   (LCS)
          dp[i][j] = max(dp[i+1][j], dp[i][j-1])   (LPS, fill backwards)

Subsequence vs Substring vs Subarray

Longest Common Subsequence (LCS)

Problem (LeetCode 1143): Given text1 and text2, return the length of their longest common subsequence.

State: dp[i][j] = LCS length of text1[0..i−1] and text2[0..j−1].

Recurrence:

• If text1[i−1] == text2[j−1]: dp[i][j] = dp[i−1][j−1] + 1
• Else: dp[i][j] = max(dp[i−1][j], dp[i][j−1])

Answer: dp[m][n] where m, n are string lengths.

LCS Code (C, Java, Python)

Python

def longest_common_subsequence(text1, text2):
    """LeetCode 1143 — LCS length of two strings. O(m × n)."""
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1   # match: extend LCS
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])  # skip one char

    return dp[m][n]


if __name__ == "__main__":
    tests = [("abcde", "ace"), ("abc", "abc"), ("abc", "def")]
    for t1, t2 in tests:
        print(f"LCS('{t1}', '{t2}') = {longest_common_subsequence(t1, t2)}")

Java

public class LongestCommonSubsequence {

    /** LCS length — classic 2D DP on string prefixes. */
    public static int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        System.out.println(longestCommonSubsequence("abcde", "ace")); // 3
        System.out.println(longestCommonSubsequence("abc", "abc"));     // 3
        System.out.println(longestCommonSubsequence("abc", "def"));   // 0
    }
}

C

#include <stdio.h>
#include <string.h>

#define MAX 1001

int max2(int a, int b) { return a > b ? a : b; }

/* LCS length of two null-terminated strings */
int lcs(char *text1, char *text2) {
    int dp[MAX][MAX];
    int m = (int)strlen(text1), n = (int)strlen(text2);
    int i, j;

    for (i = 0; i <= m; i++) dp[i][0] = 0;
    for (j = 0; j <= n; j++) dp[0][j] = 0;

    for (i = 1; i <= m; i++) {
        for (j = 1; j <= n; j++) {
            if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max2(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

int main(void) {
    printf("%d\n", lcs("abcde", "ace")); /* 3 */
    printf("%d\n", lcs("abc", "abc")); /* 3 */
    printf("%d\n", lcs("abc", "def")); /* 0 */
    return 0;
}

LCS Output & Trace

Program output (all three languages)

DP table trace — text1 = "abcde", text2 = "ace"

Longest Palindromic Subsequence

Problem (LeetCode 516): Find the length of the longest subsequence of s that reads the same forward and backward.

State: dp[i][j] = LPS length in substring s[i..j].

Recurrence:

• Base: dp[i][i] = 1 (single character)
• If s[i] == s[j]: dp[i][j] = dp[i+1][j−1] + 2
• Else: dp[i][j] = max(dp[i+1][j], dp[i][j−1])

Fill i from bottom to top so inner subproblems are ready.

LPS Code (C, Java, Python)

Python

def longest_palindrome_subseq(s):
    """LeetCode 516 — longest palindromic subsequence length."""
    n = len(s)
    dp = [[0] * n for _ in range(n)]

    for i in range(n - 1, -1, -1):
        dp[i][i] = 1
        for j in range(i + 1, n):
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2   # pair outer chars
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

    return dp[0][n - 1]


if __name__ == "__main__":
    for s in ["bbbab", "cbbd", "a"]:
        print(f"LPS('{s}') = {longest_palindrome_subseq(s)}")

Java

public class LongestPalindromeSubseq {

    public static int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];

        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][n - 1];
    }

    public static void main(String[] args) {
        System.out.println(longestPalindromeSubseq("bbbab")); // 4
        System.out.println(longestPalindromeSubseq("cbbd"));  // 2
        System.out.println(longestPalindromeSubseq("a"));    // 1
    }
}

C

#include <stdio.h>
#include <string.h>

#define MAX 1001

int max2(int a, int b) { return a > b ? a : b; }

int lps(char *s) {
    int dp[MAX][MAX];
    int n = (int)strlen(s);
    int i, j;

    for (i = n - 1; i >= 0; i--) {
        dp[i][i] = 1;
        for (j = i + 1; j < n; j++) {
            if (s[i] == s[j]) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = max2(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[0][n - 1];
}

int main(void) {
    printf("%d\n", lps("bbbab")); /* 4 */
    printf("%d\n", lps("cbbd"));  /* 2 */
    printf("%d\n", lps("a"));     /* 1 */
    return 0;
}

LPS Output & Trace

Program output

Key cells — s = "bbbab" (indices 0..4)

Related Subsequence Problems

See also longest increasing subsequence for subsequence on numeric arrays (1D, not 2D string DP).

Space Optimization

LCS depends only on the previous row — compress to O(n) space:

2D: dp[i][j] from row i-1 and column j-1
1D: prev[j] and curr[j]; iterate i = 1..m, j = 1..n
     match: curr[j] = prev[j-1] + 1
     else:   curr[j] = max(prev[j], curr[j-1])

LPS: interval DP needs full table (or O(n²) with careful ordering)
     — harder to optimize to O(n) without losing reconstruction

More Examples

Example 1: LCS → min deletions (LeetCode 583)

Min deletions to make equal = (m − LCS) + (n − LCS) = m + n − 2·LCS.

Example 2: No common subsequence

Example 3: Complexity summary

Approach Comparison

Real-Life Applications

Interview Tips

1. Clarify: subsequence (gaps OK) vs substring (contiguous) vs palindrome constraint.
2. Define dp[i][j] in words before writing loops — prefix vs substring range.
3. Draw the small LCS table for "ace" vs "abcde" on the whiteboard.
4. For LPS: fill i from n−1 down to 0; base case dp[i][i]=1.
5. Follow-ups: reconstruct LCS (backtrack from dp[m][n]); O(n) space for LCS.
6. Connect delete-operation (583) to LCS: deletions = m + n − 2·LCS.
7. Do not confuse LCS with edit distance — replace costs extra.
8. State complexity O(m × n) time explicitly.