longestCommonSubsequence<T> function

List<T> longestCommonSubsequence<T>(List<T> a, List<T> b)

Returns one longest common subsequence of a and b, compared with ==.

When several subsequences share the maximum length, one of them is returned (the one favored by the standard bottom-up backtrack). Returns an empty list when either input is empty or nothing is shared.

Runs in O(a.length * b.length) time and space.

Example:

longestCommonSubsequence(['a','b','c','d'], ['b','d']); // ['b', 'd']
longestCommonSubsequence([1,2,3], [4,5]); // []

Audited: 2026-06-12 11:26 EDT

Implementation

List<T> longestCommonSubsequence<T>(List<T> a, List<T> b) {
  if (a.isEmpty || b.isEmpty) {
    return <T>[];
  }

  final int n = a.length;
  final int m = b.length;

  // dp[i][j] = LCS length of a[i..] and b[j..]. The extra row/column of zeros
  // at n and m removes the need for bounds checks in the recurrence.
  final List<List<int>> dp = List<List<int>>.generate(
    n + 1,
    (_) => List<int>.filled(m + 1, 0),
  );
  for (int i = n - 1; i >= 0; i--) {
    for (int j = m - 1; j >= 0; j--) {
      if (a[i] == b[j]) {
        dp[i][j] = dp[i + 1][j + 1] + 1;
      } else {
        final int down = dp[i + 1][j];
        final int right = dp[i][j + 1];
        dp[i][j] = down > right ? down : right;
      }
    }
  }

  // Walk the table from the top-left, taking a matched element whenever the
  // characters are equal and otherwise stepping toward the larger subproblem.
  final List<T> result = <T>[];
  int i = 0;
  int j = 0;
  while (i < n && j < m) {
    if (a[i] == b[j]) {
      result.add(a[i]);
      i++;
      j++;
    } else if (dp[i + 1][j] >= dp[i][j + 1]) {
      i++;
    } else {
      j++;
    }
  }
  return result;
}