Autocoder

Longest Common Subsequence (LCS) Interview Questions

Last updated 2026-11-19

The longest common subsequence of two strings is the longest sequence of characters that appears in both in the same order, with gaps allowed. The two-dimensional table behind it is the template for a whole family of string problems, so understanding it well pays off in many questions.

This page works through LCS and its relatives: printing the sequence, substring, palindromic subsequence, supersequence, distinct subsequences and interleaving. Each problem has Python and Java code, complexity and edge cases. For edit-style problems see edit distance and string DP, and for the general method see dynamic programming interview questions.

Tabledp[i][j] over two prefixes
TimeO(m * n)
SpaceO(min(m, n)) for the length only
FamilySupersequence, palindrome, deletions

The pattern and when to spot it

Whenever two strings or sequences are compared and the question asks about what they share or how to make one match the other by deleting or inserting, think of an LCS table. The state is a pair of prefix lengths. A match extends the diagonal; a mismatch takes the better of skipping a character from either string.

Many questions reduce to it. The longest palindromic subsequence is LCS with the reversed string. Minimum insertions and deletions follow from lengths minus LCS. The shortest common supersequence has length m + n minus LCS. If the problem asks for contiguity, the recurrence changes: a mismatch resets the run to zero and the answer is the maximum cell, which gives the longest common substring. To print the answer you need the whole table, or a divide and conquer variant to save memory.

Common mistakes

Longest Common Subsequence (LCS) Interview Questions: questions with worked answers

  1. 1

    Is one string a subsequence of another?

    easy

    Walk through the longer string with a pointer into the shorter one, advancing the pointer whenever characters match. If the pointer reaches the end of the pattern, it is a subsequence. No table is needed because the order is fixed. Time O(n), space O(1). Edge cases: empty pattern (always true), pattern longer than the text (false), repeated characters. For many patterns against one text, precompute next-occurrence tables.

    python
    def is_subsequence(s, t):
        i = 0
        for ch in t:
            if i < len(s) and s[i] == ch:
                i += 1
        return i == len(s)
    java
    boolean isSubsequence(String s, String t) {
        int i = 0;
        for (int k = 0; k < t.length() && i < s.length(); k++)
            if (s.charAt(i) == t.charAt(k)) i++;
        return i == s.length();
    }
  2. 2

    Longest common subsequence: length

    medium

    Let dp[i][j] be the LCS length of the first i characters of a and the first j of b. If a[i-1] equals b[j-1], extend the diagonal: dp[i-1][j-1] + 1. Otherwise take the better of dropping one character from either side: max(dp[i-1][j], dp[i][j-1]). Only the previous row is needed for the length. Time O(m * n), space O(min(m, n)) with two rows. Edge cases: empty strings (0), identical strings (full length), no common character (0), subsequence versus substring.

    python
    def lcs_length(a, b):
        if len(b) > len(a):
            a, b = b, a
        prev = [0] * (len(b) + 1)
        for x in a:
            cur = [0]
            for j, y in enumerate(b, 1):
                cur.append(prev[j - 1] + 1 if x == y else max(prev[j], cur[j - 1]))
            prev = cur
        return prev[-1]
    java
    int lcsLength(String a, String b) {
        int[] prev = new int[b.length() + 1];
        for (int i = 1; i <= a.length(); i++) {
            int[] cur = new int[b.length() + 1];
            for (int j = 1; j <= b.length(); j++)
                cur[j] = a.charAt(i - 1) == b.charAt(j - 1) ? prev[j - 1] + 1 : Math.max(prev[j], cur[j - 1]);
            prev = cur;
        }
        return prev[b.length()];
    }
  3. 3

    Print an actual longest common subsequence

    medium

    Keep the full table. Then walk back from dp[m][n]: if the characters match, take that character and move diagonally; otherwise move in the direction of the larger neighbour (up or left). Reverse the collected characters at the end. Time O(m * n), space O(m * n). Edge cases: several valid answers (any is fine unless a tie-break rule is given), empty result, long inputs where the table is too large and Hirschberg divide and conquer is used.

    python
    def lcs_string(a, b):
        m, n = len(a), len(b)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                dp[i][j] = dp[i-1][j-1] + 1 if a[i-1] == b[j-1] else max(dp[i-1][j], dp[i][j-1])
        out, i, j = [], m, n
        while i and j:
            if a[i-1] == b[j-1]:
                out.append(a[i-1]); i -= 1; j -= 1
            elif dp[i-1][j] >= dp[i][j-1]:
                i -= 1
            else:
                j -= 1
        return ''.join(reversed(out))
    java
    String lcsString(String a, String b) {
        int m = a.length(), n = b.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                dp[i][j] = a.charAt(i-1) == b.charAt(j-1) ? dp[i-1][j-1] + 1 : Math.max(dp[i-1][j], dp[i][j-1]);
        StringBuilder sb = new StringBuilder();
        for (int i = m, j = n; i > 0 && j > 0; ) {
            if (a.charAt(i-1) == b.charAt(j-1)) { sb.append(a.charAt(i-1)); i--; j--; }
            else if (dp[i-1][j] >= dp[i][j-1]) i--;
            else j--;
        }
        return sb.reverse().toString();
    }
  4. 4

    Longest common substring

    medium

    A substring must be contiguous, so a mismatch resets the run. dp[i][j] is the length of the common suffix ending at a[i-1] and b[j-1]: dp[i-1][j-1] + 1 on a match and 0 otherwise. The answer is the maximum entry, not the corner. Keep the end index to extract the substring. Time O(m * n), space O(n) with a rolling row. Edge cases: no common character (empty), the maximum not at dp[m][n], resetting to 0 rather than taking a maximum on mismatch.

    python
    def longest_common_substring(a, b):
        best, end = 0, 0
        prev = [0] * (len(b) + 1)
        for i in range(1, len(a) + 1):
            cur = [0] * (len(b) + 1)
            for j in range(1, len(b) + 1):
                if a[i-1] == b[j-1]:
                    cur[j] = prev[j-1] + 1
                    if cur[j] > best:
                        best, end = cur[j], i
            prev = cur
        return a[end - best:end]
    java
    String longestCommonSubstring(String a, String b) {
        int best = 0, end = 0;
        int[] prev = new int[b.length() + 1];
        for (int i = 1; i <= a.length(); i++) {
            int[] cur = new int[b.length() + 1];
            for (int j = 1; j <= b.length(); j++)
                if (a.charAt(i-1) == b.charAt(j-1)) {
                    cur[j] = prev[j-1] + 1;
                    if (cur[j] > best) { best = cur[j]; end = i; }
                }
            prev = cur;
        }
        return a.substring(end - best, end);
    }
  5. 5

    Longest palindromic subsequence

    medium

    A palindromic subsequence reads the same forwards and backwards, so the longest one in s is the longest common subsequence of s and its reverse. Compute LCS with the reversed string. Time O(n^2), space O(n). Edge cases: single character (1), all identical (n), no repeated letters (1), do not confuse with the longest palindromic substring.

    python
    def longest_palindromic_subsequence(s):
        t = s[::-1]
        prev = [0] * (len(s) + 1)
        for x in s:
            cur = [0]
            for j, y in enumerate(t, 1):
                cur.append(prev[j - 1] + 1 if x == y else max(prev[j], cur[j - 1]))
            prev = cur
        return prev[-1]
    java
    int longestPalindromicSubsequence(String s) {
        String t = new StringBuilder(s).reverse().toString();
        int n = s.length();
        int[] prev = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int[] cur = new int[n + 1];
            for (int j = 1; j <= n; j++)
                cur[j] = s.charAt(i-1) == t.charAt(j-1) ? prev[j-1] + 1 : Math.max(prev[j], cur[j-1]);
            prev = cur;
        }
        return prev[n];
    }
  6. 6

    Minimum insertions to make a string a palindrome

    medium

    Characters already inside a longest palindromic subsequence need no partner. Every other character needs one inserted copy. So the answer is n minus the length of the longest palindromic subsequence. Time O(n^2), space O(n). Edge cases: already a palindrome (0), no repeated letters (n - 1), empty string.

    python
    def min_insertions(s):
        t = s[::-1]
        prev = [0] * (len(s) + 1)
        for x in s:
            cur = [0]
            for j, y in enumerate(t, 1):
                cur.append(prev[j - 1] + 1 if x == y else max(prev[j], cur[j - 1]))
            prev = cur
        return len(s) - prev[-1]
    java
    int minInsertions(String s) {
        String t = new StringBuilder(s).reverse().toString();
        int n = s.length();
        int[] prev = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int[] cur = new int[n + 1];
            for (int j = 1; j <= n; j++)
                cur[j] = s.charAt(i-1) == t.charAt(j-1) ? prev[j-1] + 1 : Math.max(prev[j], cur[j-1]);
            prev = cur;
        }
        return n - prev[n];
    }
  7. 7

    Delete operations to make two strings equal

    medium

    You can only delete characters, so what remains must be a common subsequence, and the best choice keeps the longest one. The minimum number of deletions is m + n - 2 * LCS. Time O(m * n), space O(n). Edge cases: identical strings (0), no common letters (m + n), one empty string.

    python
    def min_distance(a, b):
        prev = [0] * (len(b) + 1)
        for x in a:
            cur = [0]
            for j, y in enumerate(b, 1):
                cur.append(prev[j - 1] + 1 if x == y else max(prev[j], cur[j - 1]))
            prev = cur
        return len(a) + len(b) - 2 * prev[-1]
    java
    int minDistance(String a, String b) {
        int[] prev = new int[b.length() + 1];
        for (int i = 1; i <= a.length(); i++) {
            int[] cur = new int[b.length() + 1];
            for (int j = 1; j <= b.length(); j++)
                cur[j] = a.charAt(i-1) == b.charAt(j-1) ? prev[j-1] + 1 : Math.max(prev[j], cur[j-1]);
            prev = cur;
        }
        return a.length() + b.length() - 2 * prev[b.length()];
    }
  8. 8

    Shortest common supersequence

    hard

    The shortest string containing both inputs as subsequences has length m + n - LCS. To build it, walk the LCS table backwards: on a match emit that character once; otherwise emit the character from the side you are leaving. When one string runs out, emit the rest of the other. Reverse at the end. Time O(m * n), space O(m * n). Edge cases: one string being a subsequence of the other (the longer string), disjoint alphabets (concatenation), several valid answers.

    python
    def shortest_supersequence(a, b):
        m, n = len(a), len(b)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                dp[i][j] = dp[i-1][j-1] + 1 if a[i-1] == b[j-1] else max(dp[i-1][j], dp[i][j-1])
        out, i, j = [], m, n
        while i and j:
            if a[i-1] == b[j-1]:
                out.append(a[i-1]); i -= 1; j -= 1
            elif dp[i-1][j] >= dp[i][j-1]:
                out.append(a[i-1]); i -= 1
            else:
                out.append(b[j-1]); j -= 1
        while i:
            out.append(a[i-1]); i -= 1
        while j:
            out.append(b[j-1]); j -= 1
        return ''.join(reversed(out))
    java
    String shortestSupersequence(String a, String b) {
        int m = a.length(), n = b.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                dp[i][j] = a.charAt(i-1) == b.charAt(j-1) ? dp[i-1][j-1] + 1 : Math.max(dp[i-1][j], dp[i][j-1]);
        StringBuilder sb = new StringBuilder();
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (a.charAt(i-1) == b.charAt(j-1)) { sb.append(a.charAt(i-1)); i--; j--; }
            else if (dp[i-1][j] >= dp[i][j-1]) sb.append(a.charAt(--i));
            else sb.append(b.charAt(--j));
        }
        while (i > 0) sb.append(a.charAt(--i));
        while (j > 0) sb.append(b.charAt(--j));
        return sb.reverse().toString();
    }
  9. 9

    Distinct subsequences: how many times does t occur in s?

    hard

    Let dp[j] be the number of ways to form the first j characters of t from the part of s seen so far, with dp[0] = 1. For each character c of s, update j from high to low: if t[j-1] == c, add dp[j-1]. Going downward stops one character of s being used twice in the same step. Time O(m * n), space O(n). Edge cases: t longer than s (0), empty t (1), repeated characters multiplying the count, results exceeding int range (use long).

    python
    def num_distinct(s, t):
        dp = [1] + [0] * len(t)
        for c in s:
            for j in range(len(t), 0, -1):
                if t[j - 1] == c:
                    dp[j] += dp[j - 1]
        return dp[len(t)]
    java
    long numDistinct(String s, String t) {
        long[] dp = new long[t.length() + 1];
        dp[0] = 1;
        for (char c : s.toCharArray())
            for (int j = t.length(); j >= 1; j--)
                if (t.charAt(j - 1) == c) dp[j] += dp[j - 1];
        return dp[t.length()];
    }
  10. 10

    Interleaving string: can s3 be formed by interleaving s1 and s2?

    hard

    dp[i][j] is true if the first i + j characters of s3 can be formed from the first i of s1 and first j of s2. It is true if the last character of s3 matches s1[i-1] and dp[i-1][j] holds, or matches s2[j-1] and dp[i][j-1] holds. Reject immediately if the lengths do not add up. Time O(m * n), space O(n) rolling. Edge cases: length mismatch (false), empty strings, characters that match both strings (the DP tries both), order inside each string must be kept.

    python
    def is_interleave(s1, s2, s3):
        m, n = len(s1), len(s2)
        if m + n != len(s3):
            return False
        dp = [False] * (n + 1)
        dp[0] = True
        for j in range(1, n + 1):
            dp[j] = dp[j - 1] and s2[j - 1] == s3[j - 1]
        for i in range(1, m + 1):
            dp[0] = dp[0] and s1[i - 1] == s3[i - 1]
            for j in range(1, n + 1):
                dp[j] = ((dp[j] and s1[i - 1] == s3[i + j - 1]) or
                         (dp[j - 1] and s2[j - 1] == s3[i + j - 1]))
        return dp[n]
    java
    boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length(), n = s2.length();
        if (m + n != s3.length()) return false;
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for (int j = 1; j <= n; j++) dp[j] = dp[j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
        for (int i = 1; i <= m; i++) {
            dp[0] = dp[0] && s1.charAt(i - 1) == s3.charAt(i - 1);
            for (int j = 1; j <= n; j++)
                dp[j] = (dp[j] && s1.charAt(i - 1) == s3.charAt(i + j - 1))
                     || (dp[j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
        }
        return dp[n];
    }
  11. 11

    Minimum ASCII delete sum to make two strings equal

    hard

    This is the weighted version of the deletion problem. Instead of counting characters, keep the common subsequence with the largest ASCII sum, and delete everything else. The answer is the total ASCII of both strings minus twice the best common subsequence sum. The DP is LCS where a match adds the character code rather than 1. Time O(m * n), space O(n). Edge cases: identical strings (0), no common letters (sum of both), one empty string.

    python
    def minimum_delete_sum(a, b):
        prev = [0] * (len(b) + 1)
        for x in a:
            cur = [0]
            for j, y in enumerate(b, 1):
                cur.append(prev[j - 1] + ord(x) if x == y else max(prev[j], cur[j - 1]))
            prev = cur
        return sum(map(ord, a)) + sum(map(ord, b)) - 2 * prev[-1]
    java
    int minimumDeleteSum(String a, String b) {
        int[] prev = new int[b.length() + 1];
        int total = 0;
        for (char c : a.toCharArray()) total += c;
        for (char c : b.toCharArray()) total += c;
        for (int i = 1; i <= a.length(); i++) {
            int[] cur = new int[b.length() + 1];
            for (int j = 1; j <= b.length(); j++)
                cur[j] = a.charAt(i-1) == b.charAt(j-1) ? prev[j-1] + a.charAt(i-1) : Math.max(prev[j], cur[j-1]);
            prev = cur;
        }
        return total - 2 * prev[b.length()];
    }
  12. 12

    Longest common subsequence of three strings

    hard

    Extend the table to three dimensions: dp[i][j][k] is the LCS of the three prefixes. If the three last characters match, add 1 to dp[i-1][j-1][k-1]. Otherwise take the maximum of dropping the last character from one of the three strings. Time O(a * b * c), space O(a * b * c), or O(b * c) with rolling layers. Edge cases: one empty string (0), all three identical, cubic growth means inputs are small.

    python
    def lcs3(a, b, c):
        A, B, C = len(a), len(b), len(c)
        dp = [[[0] * (C + 1) for _ in range(B + 1)] for _ in range(A + 1)]
        for i in range(1, A + 1):
            for j in range(1, B + 1):
                for k in range(1, C + 1):
                    if a[i-1] == b[j-1] == c[k-1]:
                        dp[i][j][k] = dp[i-1][j-1][k-1] + 1
                    else:
                        dp[i][j][k] = max(dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1])
        return dp[A][B][C]
    java
    int lcs3(String a, String b, String c) {
        int A = a.length(), B = b.length(), C = c.length();
        int[][][] dp = new int[A + 1][B + 1][C + 1];
        for (int i = 1; i <= A; i++)
            for (int j = 1; j <= B; j++)
                for (int k = 1; k <= C; k++) {
                    if (a.charAt(i-1) == b.charAt(j-1) && b.charAt(j-1) == c.charAt(k-1))
                        dp[i][j][k] = dp[i-1][j-1][k-1] + 1;
                    else
                        dp[i][j][k] = Math.max(dp[i-1][j][k], Math.max(dp[i][j-1][k], dp[i][j][k-1]));
                }
        return dp[A][B][C];
    }

Frequently asked questions

What is the difference between LCS and longest common substring?

A subsequence can skip characters, a substring must be contiguous. LCS takes the best of two neighbours on a mismatch; the substring version resets to zero and takes the maximum cell.

How do I print the LCS and not just its length?

Keep the full dp table, then walk back from the corner. On a match take the character and move diagonally; otherwise move to the neighbour with the larger value. Reverse the collected characters.

Can LCS be solved faster than O(m * n)?

In general no substantially faster algorithm is known for arbitrary strings. Bit-parallel methods speed it up by a constant factor, and Hirschberg algorithm cuts memory to linear space.

Is LCS common in interviews?

It is a classic in DP rounds, often as part of palindromic or edit-style questions. The technical interview guide covers how such rounds usually go.

Related guides

More in DSA Interview Questions

See all in this section