Longest Common Subsequence (LCS)
What Is LCS?
A subsequence is a sequence that appears in the same order in the original string but not necessarily contiguously. The Longest Common Subsequence is the longest such sequence appearing in both strings.
SUBSEQUENCE vs SUBSTRING:
s1 = "abcde"
Subsequence "ace": indices 0,2,4 → skip b,d — valid ✓
Substring "bcd": indices 1,2,3 → contiguous — valid ✓
Subsequence "aec": a at 0, e at 4, c at 2 → OUT OF ORDER — invalid ✗
LCS of s1="abcde" and s2="ace":
Common subsequences: "a","c","e","ac","ae","ce","ace"
Longest: "ace" (length 3)
LCS of s1="AGGTAB" and s2="GXTXAYB":
LCS = "GTAB" (length 4) — not unique ("GTAB", "GXAB"... check carefully)
Actually: A_G_T_A_B / G_X_T_A_Y_B → GTAB ✓
APPLICATIONS:
diff utility (compare file versions)
DNA sequence alignment
Plagiarism detection
Version control (git diff)
The DP Table
STATE: dp[i][j] = LCS length of s1[0..i-1] and s2[0..j-1]
RECUR: if s1[i-1] == s2[j-1]: dp[i][j] = 1 + dp[i-1][j-1] ← match
else: dp[i][j] = max(dp[i-1][j], ← skip s1[i-1]
dp[i][j-1]) ← skip s2[j-1]
BASE: dp[0][j] = 0 for all j (s1 is empty → LCS = 0)
dp[i][0] = 0 for all i (s2 is empty → LCS = 0)
FILL: Row by row, left to right
ANSWER: dp[m][n]
TABLE for s1="abcde" (rows), s2="ace" (cols):
"" a c e
"" [ 0, 0, 0, 0 ]
a [ 0, 1, 1, 1 ] ← s1[0]='a' matches s2[0]='a' → 1+dp[0][0]=1
b [ 0, 1, 1, 1 ] ← s1[1]='b' matches nothing
c [ 0, 1, 2, 2 ] ← s1[2]='c' matches s2[1]='c' → 1+dp[1][0]=2
d [ 0, 1, 2, 2 ] ← s1[3]='d' matches nothing
e [ 0, 1, 2, 3 ] ← s1[4]='e' matches s2[2]='e' → 1+dp[3][1]=3
LCS = dp[5][3] = 3 ✓
CELL DERIVATIONS:
dp[1][1]: s1[0]='a'==s2[0]='a' → match → 1+dp[0][0]=1
dp[3][2]: s1[2]='c'==s2[1]='c' → match → 1+dp[2][1]=1+1=2
dp[5][3]: s1[4]='e'==s2[2]='e' → match → 1+dp[4][2]=1+2=3
Backtracking: Print the Actual LCS
To find the actual LCS string (not just its length), backtrack through the table from dp[m][n].
BACKTRACKING RULES starting at dp[m][n]:
At dp[i][j]:
If s1[i-1] == s2[j-1]:
→ Characters MATCHED — include in LCS
→ Move diagonally to dp[i-1][j-1]
Else if dp[i-1][j] >= dp[i][j-1]:
→ Value came from skipping s1[i-1]
→ Move UP to dp[i-1][j]
Else:
→ Value came from skipping s2[j-1]
→ Move LEFT to dp[i][j-1]
Stop when i=0 or j=0. Reverse the collected chars.
TRACE for s1="abcde", s2="ace":
Start at dp[5][3]=3, s1[4]='e', s2[2]='e' → MATCH → collect 'e', go dp[4][2]
dp[4][2]=2, s1[3]='d', s2[1]='c' → no match, dp[3][2]=2 >= dp[4][1]=1 → go UP dp[3][2]
dp[3][2]=2, s1[2]='c', s2[1]='c' → MATCH → collect 'c', go dp[2][1]
dp[2][1]=1, s1[1]='b', s2[0]='a' → no match, dp[1][1]=1 >= dp[2][0]=0 → go UP dp[1][1]
dp[1][1]=1, s1[0]='a', s2[0]='a' → MATCH → collect 'a', go dp[0][0]
dp[0][0] — stop (i=0)
Collected: ['e','c','a'] → Reversed: "ace" ✓
Full LCS Implementation
1import java.util.*;
2
3public class LCS {
4
5 // ── LCS Length — O(m*n) time, O(m*n) space ──────────────────────
6 public static int lcsLength(String s1, String s2) {
7 int m = s1.length(), n = s2.length();
8 int[][] dp = new int[m+1][n+1];
9
10 for (int i=1; i<=m; i++) {
11 for (int j=1; j<=n; j++) {
12 if (s1.charAt(i-1) == s2.charAt(j-1))
13 dp[i][j] = 1 + dp[i-1][j-1]; // Match
14 else
15 dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); // Skip
16 }
17 }
18 return dp[m][n];
19 }
20
21 // ── Print LCS — backtrack through dp table ───────────────────────
22 public static String printLCS(String s1, String s2) {
23 int m = s1.length(), n = s2.length();
24 int[][] dp = new int[m+1][n+1];
25
26 // Build dp table
27 for (int i=1; i<=m; i++)
28 for (int j=1; j<=n; j++)
29 dp[i][j] = s1.charAt(i-1)==s2.charAt(j-1)
30 ? 1 + dp[i-1][j-1]
31 : Math.max(dp[i-1][j], dp[i][j-1]);
32
33 // Backtrack to find the actual LCS
34 StringBuilder lcs = new StringBuilder();
35 int i=m, j=n;
36 while (i>0 && j>0) {
37 if (s1.charAt(i-1) == s2.charAt(j-1)) {
38 lcs.append(s1.charAt(i-1)); // Match: include character
39 i--; j--;
40 } else if (dp[i-1][j] >= dp[i][j-1]) {
41 i--; // Came from above
42 } else {
43 j--; // Came from left
44 }
45 }
46 return lcs.reverse().toString(); // Reverse to get correct order
47 }
48
49 // ── LCS Length — O(n) space with rolling row ─────────────────────
50 public static int lcsSpaceOpt(String s1, String s2) {
51 int m = s1.length(), n = s2.length();
52 int[] prev = new int[n+1], curr = new int[n+1];
53
54 for (int i=1; i<=m; i++) {
55 for (int j=1; j<=n; j++) {
56 if (s1.charAt(i-1) == s2.charAt(j-1))
57 curr[j] = 1 + prev[j-1]; // prev[j-1] = dp[i-1][j-1]
58 else
59 curr[j] = Math.max(prev[j], curr[j-1]);
60 }
61 int[] tmp = prev; prev = curr; curr = tmp; // Roll
62 Arrays.fill(curr, 0);
63 }
64 return prev[n];
65 }
66
67 // ── Shortest Common Supersequence Length ─────────────────────────
68 // SCS contains all chars of both strings (LCS chars merged)
69 public static int scsLength(String s1, String s2) {
70 return s1.length() + s2.length() - lcsLength(s1, s2);
71 }
72
73 // ── Print Shortest Common Supersequence ──────────────────────────
74 public static String printSCS(String s1, String s2) {
75 int m = s1.length(), n = s2.length();
76 int[][] dp = new int[m+1][n+1];
77 for (int i=1;i<=m;i++) for (int j=1;j<=n;j++)
78 dp[i][j] = s1.charAt(i-1)==s2.charAt(j-1)
79 ? 1+dp[i-1][j-1] : Math.max(dp[i-1][j], dp[i][j-1]);
80
81 // Backtrack: include BOTH strings' characters, shared once
82 StringBuilder scs = new StringBuilder();
83 int i=m, j=n;
84 while (i>0 && j>0) {
85 if (s1.charAt(i-1) == s2.charAt(j-1)) {
86 scs.append(s1.charAt(i-1)); // Shared char — add once
87 i--; j--;
88 } else if (dp[i-1][j] >= dp[i][j-1]) {
89 scs.append(s1.charAt(i-1)); i--; // s1 char not in LCS
90 } else {
91 scs.append(s2.charAt(j-1)); j--; // s2 char not in LCS
92 }
93 }
94 while (i>0) { scs.append(s1.charAt(i-1)); i--; }
95 while (j>0) { scs.append(s2.charAt(j-1)); j--; }
96 return scs.reverse().toString();
97 }
98
99 // ── Longest Palindromic Subsequence ──────────────────────────────
100 // LPS(s) = LCS(s, reverse(s))
101 public static int longestPalindromicSubseq(String s) {
102 String rev = new StringBuilder(s).reverse().toString();
103 return lcsLength(s, rev);
104 }
105
106 // ── Minimum Insertions to Make Palindrome ────────────────────────
107 // min_insertions = len(s) - LPS(s)
108 public static int minInsertionsPalindrome(String s) {
109 return s.length() - longestPalindromicSubseq(s);
110 }
111
112 // ── Longest Common Substring (contiguous) ────────────────────────
113 public static int longestCommonSubstring(String s1, String s2) {
114 int m=s1.length(), n=s2.length(), maxLen=0;
115 int[][] dp = new int[m+1][n+1];
116
117 for (int i=1; i<=m; i++) {
118 for (int j=1; j<=n; j++) {
119 if (s1.charAt(i-1) == s2.charAt(j-1)) {
120 dp[i][j] = 1 + dp[i-1][j-1]; // Extend contiguous match
121 maxLen = Math.max(maxLen, dp[i][j]);
122 }
123 // else: dp[i][j] = 0 (default) — reset on mismatch
124 }
125 }
126 return maxLen;
127 }
128
129 public static void main(String[] args) {
130 String s1 = "abcde", s2 = "ace";
131 System.out.println("LCS length: " + lcsLength(s1, s2)); // 3
132 System.out.println("LCS string: " + printLCS(s1, s2)); // ace
133 System.out.println("LCS space-opt: " + lcsSpaceOpt(s1, s2)); // 3
134 System.out.println("SCS length: " + scsLength(s1, s2)); // 7
135 System.out.println("SCS string: " + printSCS(s1, s2)); // abcde
136
137 String pal = "bbbab";
138 System.out.println("LPS(bbbab): " + longestPalindromicSubseq(pal)); // 4
139 System.out.println("MinInsert(bbbab): " + minInsertionsPalindrome(pal)); // 1
140
141 System.out.println("LCSubstring: " +
142 longestCommonSubstring("abcxyz","xyzabc")); // 3
143 }
144}Output:
LCS length: 3
LCS string: ace
LCS space-opt: 3
SCS length: 7
SCS string: abcde
LPS(bbbab): 4
MinInsert(bbbab): 1
LCSubstring: 3
LCS vs Longest Common Substring
PROBLEM RECUR ON MISMATCH ANSWER LOCATION RESET ON MISMATCH
LCS (subsequence) max(dp[i-1][j],dp[i][j-1]) dp[m][n] No — carry forward
Longest Com. Substr. dp[i][j] = 0 max over ALL cells Yes — reset to 0
(contiguous)
TABLE for s1="abcxyz", s2="xyzabc":
LCS table: LCS Substring table:
"" x y z a b c "" x y z a b c
"" [ 0, 0, 0, 0, 0, 0, 0 ] "" [ 0, 0, 0, 0, 0, 0, 0 ]
a [ 0, 0, 0, 0, 1, 1, 1 ] a [ 0, 0, 0, 0, 1, 0, 0 ]
b [ 0, 0, 0, 0, 1, 2, 2 ] b [ 0, 0, 0, 0, 0, 2, 0 ]
c [ 0, 0, 0, 0, 1, 2, 3 ] c [ 0, 0, 0, 0, 0, 0, 3 ] ← max=3
x [ 0, 1, 1, 1, 1, 2, 3 ] x [ 0, 1, 0, 0, 0, 0, 0 ]
y [ 0, 1, 2, 2, 2, 2, 3 ] y [ 0, 0, 2, 0, 0, 0, 0 ]
z [ 0, 1, 2, 3, 3, 3, 3 ] z [ 0, 0, 0, 3, 0, 0, 0 ] ← max=3
LCS = dp[6][6] = 3 LCS Substring = max cell = 3
LCS = "abc" or "xyz" Substring = "abc" or "xyz"
Both 3 here, but try s1="abc",s2="cbda":
LCS=2 ("bc" — non-contiguous, skip c→b)
LCS Substring=1 ("b" or "c" — no contiguous match longer than 1)
The LCS Family: Related Problems
PROBLEM RELATIONSHIP TO LCS FORMULA ────────────────────────────────────────────────────────────────────────── LCS length Base problem dp[m][n] Print LCS Backtrack dp table Collect on diagonal moves Longest Common Substring Contiguous LCS dp[i][j]=0 on mismatch; max cell Shortest Common Superseq. Merge both, share LCS |s1|+|s2|-LCS; backtrack both Edit Distance Transform s1 into s2 Not directly LCS, but same table shape Longest Palindromic Subseq. LPS = LCS(s, reverse(s)) LCS(s, rev(s)) Min Insertions Palindrome Complement of LPS len(s) - LPS(s) Min Deletions (LCS) Keep LCS, delete rest |s1|-LCS + |s2|-LCS Longest Repeating Subseq. LCS(s,s) no same-index use Modified LCS: i!=j condition
Shortest Common Supersequence — Backtracking
SCS BACKTRACK differs from LCS backtrack:
LCS: include character ONLY on diagonal (both chars same)
SCS: include character on EVERY move — diag once, else from whichever path
RULES:
If s1[i-1]==s2[j-1]: include ONCE, move diagonal
If moved UP (i--): include s1[i] character (it's in SCS but not LCS)
If moved LEFT (j--): include s2[j] character
After loop: append remaining chars from s1 or s2
TRACE for s1="abcde", s2="ace":
LCS table (same as before):
"" a c e
"" [ 0, 0, 0, 0 ]
a [ 0, 1, 1, 1 ]
b [ 0, 1, 1, 1 ]
c [ 0, 1, 2, 2 ]
d [ 0, 1, 2, 2 ]
e [ 0, 1, 2, 3 ]
Start i=5,j=3:
s1[4]='e'==s2[2]='e' → include 'e', i=4,j=2
s1[3]='d'!=s2[1]='c': dp[3][2]=2>=dp[4][1]=1 → UP → include s1[3]='d', i=3
s1[2]='c'==s2[1]='c' → include 'c', i=2,j=1
s1[1]='b'!=s2[0]='a': dp[1][1]=1>=dp[2][0]=0 → UP → include s1[1]='b', i=1
s1[0]='a'==s2[0]='a' → include 'a', i=0,j=0
Collected (reversed): "abcde"
SCS = "abcde" (already a supersequence of both!) length 5.
But SCS formula gives |s1|+|s2|-LCS = 5+3-3 = 5 ✓
Space Optimisation
FULL TABLE (O(m×n)):
Needed for: Print LCS (backtracking requires full table)
Print SCS (backtracking requires full table)
Not needed: Just the length
ROLLING ROW (O(n)):
For LCS LENGTH only (no backtracking needed)
dp[i][j] depends on dp[i-1][j], dp[i-1][j-1], dp[i][j-1]
Keep only prev[] (row i-1) and curr[] (row i being built)
CAREFUL: dp[i-1][j-1] is the DIAGONAL of prev[].
When computing curr[j], need prev[j-1] (already in prev[]).
For LCS: curr[j] = 1+prev[j-1] (match) or max(prev[j],curr[j-1]) (no match)
All dependencies available naturally in left-to-right scan.
CANNOT PRINT LCS with O(n) space without O(m+n) reconstruction path.
If you need the actual sequence: keep the O(m×n) table or use Hirschberg's O(n) algorithm.
Complexity Summary
| Problem | Time | Space | Space Optimised |
|---|---|---|---|
| LCS length | O(m×n) | O(m×n) | O(n) rolling row |
| Print LCS | O(m×n) | O(m×n) | Cannot (needs full table) |
| LCS Substring | O(m×n) | O(m×n) | O(n) rolling row |
| SCS length | O(m×n) | O(m×n) | O(n) |
| Print SCS | O(m×n) | O(m×n) | Cannot (needs full table) |
| LPS | O(n²) | O(n²) | O(n) rolling row |
| Min Insertions Palindrome | O(n²) | O(n²) | O(n) |
Common Mistakes
LCS answer at dp[m][n], not max of all cells. For LCS, the full answer is always at the bottom-right cell dp[m][n]. For Longest Common Substring, the answer IS the max over all cells (since dp[i][j] resets to 0 on mismatch and only tracks the length of contiguous match ending at this position). Confusing these two gives wrong answers.
Backtracking direction when dp[i-1][j] == dp[i][j-1]. When dp[i-1][j] == dp[i][j-1], either direction is valid (leads to a different but equally valid LCS). The code's choice (e.g., prefer going up) consistently finds one valid LCS. This is fine for finding A valid LCS — but if you need ALL LCS strings, you must branch both ways.
Longest Common Substring: returning dp[m][n] instead of max(dp[i][j]). dp[m][n] is the length of any common suffix of s1 and s2 (0 if last chars differ). The longest common substring ending anywhere is max(dp[i][j]). Always track a running maximum while filling.
SCS backtracking: appending remaining characters after the loop. After the main while loop (i>0 and j>0), the remaining characters in s1 (if i>0) or s2 (if j>0) must still be appended. These are unique characters not in the LCS region that must appear in the supersequence. Missing this step produces a SCS shorter than both strings.
Space-optimised LCS: losing the diagonal value. When computing curr[j] = 1 + prev[j-1] (the match case), prev[j-1] is the diagonal value dp[i-1][j-1]. This is fine because we process j left to right and haven't touched prev[j-1] yet. However, if you overwrite prev in-place (single array with right-to-left for LCS), the diagonal would be wrong — use two arrays or process carefully.
Interview Questions
Q: How does backtracking work to print the actual LCS string?
Start at dp[m][n]. At each cell dp[i][j]: if s1[i-1]==s2[j-1], this character was part of the LCS — collect it and move diagonally to dp[i-1][j-1]. Otherwise, move in the direction of the larger neighbour: if dp[i-1][j] >= dp[i][j-1], move up (i--); else move left (j--). Ties can go either way. Stop when i=0 or j=0. The collected characters are in reverse order — reverse to get the LCS. Time O(m+n) for backtracking after O(m×n) for building the table.
Q: What is the Shortest Common Supersequence and how does it relate to LCS?
The SCS of s1 and s2 is the shortest string that contains both s1 and s2 as subsequences. Length = |s1| + |s2| - LCS(s1,s2). The LCS characters are shared — they appear once in the SCS instead of twice. Intuition: merge both strings, keeping shared LCS characters merged. To print the SCS, backtrack the LCS table: on a diagonal move (match), include the character once; on an up move, include the s1 character; on a left move, include the s2 character.
Q: How does Longest Palindromic Subsequence reduce to LCS?
A string is palindromic if it equals its reverse. A palindromic subsequence of s must be a subsequence of s that also reads the same forwards and backwards — equivalently, it must appear as a subsequence in both s and reverse(s). Therefore LPS(s) = LCS(s, reverse(s)). Example: s="bbbab", reverse="babbb". LCS = "bbbb" (length 4) — the longest common subsequence is four b's, which indeed forms a palindrome.
Summary
LCS finds the longest sequence appearing in both strings in the same relative order, not necessarily contiguously.
The core DP:
- ›Match:
dp[i][j] = 1 + dp[i-1][j-1] - ›No match:
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) - ›Base: first row and column = 0
- ›Answer:
dp[m][n]
Backtracking to print LCS: diagonal move on character match (collect character); up/left move when no match (follow larger neighbour); reverse the collected result.
Five LCS-family problems:
| Problem | Insight | Formula |
|---|---|---|
| Longest Common Substring | Reset dp[i][j]=0 on mismatch; answer = max cell | Contiguous match only |
| Shortest Common Supersequence | Merge both strings, share LCS | Length = ❘s1❘+❘s2❘-LCS |
| Longest Palindromic Subsequence | Palindrome = same as its reverse | LCS(s, reverse(s)) |
| Min Insertions Palindrome | Insert to make palindrome | len(s) - LPS(s) |
| Min Deletions | Delete from both to reach LCS | ❘s1❘-LCS + ❘s2❘-LCS |
Space: O(m×n) for printing (needs full table for backtrack); O(n) rolling row for length only.
In the next topic you will explore Longest Increasing Subsequence (LIS) — the classic O(n²) DP approach and the O(n log n) patience sorting solution.
LCS of 'abcde' and 'ace' is 3. Which cell in the dp table holds this answer?