Longest Common Subsequence in Python, Java and TypeScript

The table and the walk back, printing the length and one longest common subsequence for three pairs of words.

A longest common subsequence takes two loops to fill the table and one loop to walk back from its last cell, and the listings below write both in each language. Each returns the subsequence itself, so its length is the answer's length, and runs it on MONEY and LEMON from Fill a Longest Common Subsequence Table, on KITTEN and SITTING, and on two words with nothing in common.

The longest common subsequence: fill the table, then walk back from the last cell

lcs_code.pypy

def longest_common_subsequence(a: str, b: str) -> str:
    table = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                table[i][j] = table[i - 1][j - 1] + 1
            else:
                table[i][j] = max(table[i - 1][j], table[i][j - 1])
    picked = []
    i, j = len(a), len(b)
    while i > 0 and j > 0:
        if a[i - 1] == b[j - 1]:
            picked.append(a[i - 1])
            i, j = i - 1, j - 1
        elif table[i - 1][j] >= table[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return "".join(reversed(picked))


for a, b in [("MONEY", "LEMON"), ("KITTEN", "SITTING"), ("ABC", "XYZ")]:
    common = longest_common_subsequence(a, b)
    print(f"{a}, {b}: length {len(common)}, {common or 'nothing in common'}")

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

MONEY, LEMON: length 3, MON
KITTEN, SITTING: length 4, ITTN
ABC, XYZ: length 0, nothing in common

LcsCode.javajava

public class LcsCode {
    static String longestCommonSubsequence(String a, String b) {
        int[][] table = new int[a.length() + 1][b.length() + 1];
        for (int i = 1; i <= a.length(); i++) {
            for (int j = 1; j <= b.length(); j++) {
                if (a.charAt(i - 1) == b.charAt(j - 1)) {
                    table[i][j] = table[i - 1][j - 1] + 1;
                } else {
                    table[i][j] = Math.max(table[i - 1][j], table[i][j - 1]);
                }
            }
        }
        StringBuilder picked = new StringBuilder();
        int i = a.length();
        int j = b.length();
        while (i > 0 && j > 0) {
            if (a.charAt(i - 1) == b.charAt(j - 1)) {
                picked.append(a.charAt(i - 1));
                i--;
                j--;
            } else if (table[i - 1][j] >= table[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }
        return picked.reverse().toString();
    }

    public static void main(String[] args) {
        String[][] pairs = {{"MONEY", "LEMON"}, {"KITTEN", "SITTING"}, {"ABC", "XYZ"}};
        for (String[] pair : pairs) {
            String common = longestCommonSubsequence(pair[0], pair[1]);
            String shown = common.isEmpty() ? "nothing in common" : common;
            System.out.println(pair[0] + ", " + pair[1] + ": length " + common.length() + ", " + shown);
        }
    }
}

OutputRan with eclipse-temurin:25.0.4.1_1-jdk-noble (Java 25.0.4.1)

MONEY, LEMON: length 3, MON
KITTEN, SITTING: length 4, ITTN
ABC, XYZ: length 0, nothing in common

lcs_code.tsts

function longestCommonSubsequence(a: string, b: string): string {
  const table = Array.from({ length: a.length + 1 }, () => new Array<number>(b.length + 1).fill(0));
  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      if (a[i - 1] === b[j - 1]) {
        table[i][j] = table[i - 1][j - 1] + 1;
      } else {
        table[i][j] = Math.max(table[i - 1][j], table[i][j - 1]);
      }
    }
  }
  const picked: string[] = [];
  let i = a.length;
  let j = b.length;
  while (i > 0 && j > 0) {
    if (a[i - 1] === b[j - 1]) {
      picked.push(a[i - 1]);
      i--;
      j--;
    } else if (table[i - 1][j] >= table[i][j - 1]) {
      i--;
    } else {
      j--;
    }
  }
  return picked.reverse().join("");
}

const pairs: [string, string][] = [["MONEY", "LEMON"], ["KITTEN", "SITTING"], ["ABC", "XYZ"]];
for (const [a, b] of pairs) {
  const common = longestCommonSubsequence(a, b);
  console.log(`${a}, ${b}: length ${common.length}, ${common || "nothing in common"}`);
}

OutputRan with node:24.22.0-trixie-slim (Node 24.22.0), TypeScript 5.9.3

MONEY, LEMON: length 3, MON
KITTEN, SITTING: length 4, ITTN
ABC, XYZ: length 0, nothing in common

All three printed the same lines, and a brute-force search over every subsequence of both words printed them too, and found each answer to be the only longest one. Where two longest subsequences exist, the walk back returns one of them, and which one depends on how it breaks ties.

The highlighted lines are the three decisions the code makes. The table has one more row and column than the words have letters, for the empty prefix, so the loops run from 1 and compare the letters at i − 1 and j − 1. The walk back stops when either index reaches 0, because an empty prefix shares nothing. On a mismatch it moves towards the larger neighbour, and on a tie it moves up; moving left on ties is equally correct and can return a different subsequence of the same length.

The walk collects letters from the end backwards and reverses them once at the end: Python with reversed, Java with StringBuilder.reverse and TypeScript with Array.prototype.reverse. Filling the table is O(m × n) and the walk is O(m + n), since each step reduces i, j or both.

← → move through sections and cards