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.
| Table | dp[i][j] over two prefixes |
|---|---|
| Time | O(m * n) |
| Space | O(min(m, n)) for the length only |
| Family | Supersequence, 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
- Mixing up subsequence and substring and so using the wrong mismatch rule.
- Reading the answer from the wrong cell: the corner for subsequences, the maximum for substrings.
- Mixing one-based table indexes with zero-based string indexes.
- Rolling a single row without saving the diagonal value before it is overwritten.
- Not checking lengths early for interleaving or supersequence questions.
Longest Common Subsequence (LCS) Interview Questions: questions with worked answers
1 Is one string a subsequence of another?
easyWalk 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.
pythondef is_subsequence(s, t): i = 0 for ch in t: if i < len(s) and s[i] == ch: i += 1 return i == len(s)javaboolean 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 Longest common subsequence: length
mediumLet 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.
pythondef 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]javaint 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 Print an actual longest common subsequence
mediumKeep 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.
pythondef 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))javaString 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 Longest common substring
mediumA 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.
pythondef 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]javaString 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 Longest palindromic subsequence
mediumA 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.
pythondef 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]javaint 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 Minimum insertions to make a string a palindrome
mediumCharacters 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.
pythondef 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]javaint 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 Delete operations to make two strings equal
mediumYou 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.
pythondef 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]javaint 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 Shortest common supersequence
hardThe 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.
pythondef 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))javaString 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 Distinct subsequences: how many times does t occur in s?
hardLet 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).
pythondef 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)]javalong 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 Interleaving string: can s3 be formed by interleaving s1 and s2?
harddp[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.
pythondef 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]javaboolean 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 Minimum ASCII delete sum to make two strings equal
hardThis 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.
pythondef 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]javaint 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 Longest common subsequence of three strings
hardExtend 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.
pythondef 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]javaint 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
- Longest Increasing Subsequence (LIS) Interview Questions
- LRU Cache and Design Data Structure Interview Questions
- Math and number theory interview questions with solutions
- Matrix interview questions with worked solutions
- Merge intervals pattern questions with worked solutions
- Minimum Spanning Tree Interview Questions
- Monotonic stack interview questions with worked solutions
- Prefix sum interview questions with worked solutions
- Queue and deque interview questions with worked solutions
- Recursion interview questions with worked solutions
- Segment Tree Interview Questions
- Sliding window interview questions with worked solutions