DSA-134 · FOCUSED PRACTICE

Longest Common Subsequence

Advanced · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 3994 deterministic checks. Learner drafts are not executed.

Understand the problem

Return the length of a longest sequence that is a subsequence of both a and b. Chosen code units must preserve their order in each string but do not need to be contiguous.

a and b are non-null Java Strings with at most 2000 UTF-16 code units each. Null throws NullPointerException and an excessive length throws IllegalArgumentException. Validate both strings before choosing a table orientation.
Comparison is exact and case-sensitive by charAt code units. All char values are supported without normalization. An identical supplementary Unicode symbol occupies two units and may contribute length two; the method is not defined in grapheme-cluster or code-point units.
Return only an int length, at most min(a.length(),b.length()). Empty input on either side returns zero. Strings are read-only. The optimized method stores one row, chooses the shorter string as columns, and does not retain enough information to promise a witness. The recursive baseline runs only on short test inputs.

Examples

Input: a="abcde", b="ace"
Output: 3
a,c,e appear in order in both, although they are not contiguous in abcde.
Input: a="abc", b="xyz"
Output: 0
No matching code unit can contribute.
Input: a="ab", b="ba"
Output: 1
Either a or b is common, but both cannot appear in the required order.
Input: a="😀", b="😀"
Output: 2
The identical surrogate pair contributes two UTF-16 code units under this explicit contract.

Before you start

Subsequence versus substring
Prefix grid dependencies and row compression

Recognize the structure

Neither one string position nor a global set of characters captures the remaining ordering constraints. The subproblem needs two prefix lengths. Its dependency graph is a grid: an equal final pair can extend a smaller common sequence diagonally, and a mismatch forces an omission from one side. The answer is a maximum alignment length, not substring length, character overlap, or edit cost.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 140/20,000 characters

Self-review

I can define both prefix axes and derive match and mismatch transitions.I can identify old diagonal/up versus new left during every in-place update.I can distinguish subsequences from substrings, define the text unit, and state what reconstruction needs.

Use the checklist to test your explanation. Checks apply to this visit.

Try before revealing

Hint 1

Define an optimum for two prefixes, including empty prefixes.

Hint 2

If the final code units differ, what must a common sequence omit? What happens when they match?

Hint 3

In one row, dp[j] is old up and dp[j−1] is new left; save diagonal separately.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Uncached suffix alignment recursion

For suffix starts i and j, return zero when either suffix is empty. If their next code units match, keep that pair and recurse diagonally with one added. Otherwise try skipping the next unit of a or the next unit of b and take the larger result. Mismatching branches repeatedly request the same suffix pair. A conservative upper bound is O(2^(m+n)) time and O(m+n+1) stack depth, with much less work on matching strings. Tests restrict this method to short inputs and compare it with independently enumerated subsequences recognized in the other string.

Improve the baseline

Define the complete prefix grid

L(i,j) is the longest common subsequence length of rows[0..i) and columns[0..j). Every L(0,j) and L(i,0) is zero because an empty side contributes no selected units. Use n+1 columns to represent the empty prefix explicitly, rather than special-casing the first character.

Compare final code units

If rows[i−1]==columns[j−1], an optimal alignment can pair those equal final units, giving L(i−1,j−1)+1. If they differ, any common subsequence must omit at least one of those final positions, so L(i,j)=max(L(i−1,j),L(i,j−1)). Both mismatch candidates remain valid subsequences of the larger prefixes.

Fill the full table conceptually

For abc and ac, rows of lengths 0..3 across column prefixes empty,a,ac are [0,0,0], [0,1,1], [0,1,1], [0,1,2]. A mismatch does not reset the state to zero: earlier compatible matches can persist through gaps. That reset would implement longest common substring instead.

Choose the shorter axis and compress one row

The length is symmetric, so use the shorter input as columns. Before cell (i,j), dp[j] still holds the old row’s up value while dp[j−1] already holds the current row’s left value. Keep diagonal separately as old L(i−1,j−1), save up before writing dp[j], then advance diagonal=up.

Separate score computation from reconstruction

A one-row score update destroys old decisions, which is fine for the requested length. It does not identify matched source indices. A full grid with deterministic traceback or a divide-and-conquer reconstruction is needed for one actual subsequence. Swapping the axes is harmless for the number but changes the orientation of any future returned indices.

Why it is correct

Empty-prefix boundaries

No nonempty sequence is a subsequence of an empty string. The zero-initialized row and unchanged column-zero values establish every grid boundary.

Optimal substructure

On a match, pair the equal final units in an optimum: any alignment omitting an endpoint can be adjusted to use the last equal pair without losing length. Removing the pair leaves a common sequence of the two shorter prefixes. On a mismatch, the final positions cannot both form the final matched pair, so omitting one covers every optimum. Taking the maximum of valid omission candidates is therefore exact.

Compressed-row invariant and termination

At cell entry, diagonal, up, and left refer to the exact three dependencies from the conceptual grid. Saving up before overwriting preserves the next cell’s diagonal. Increasing columns and rows evaluate all cells after their dependencies. The final dp entry equals the full-prefix optimum. All lengths fit int and caller strings are unchanged.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.Objects;

public final class Solution {
    private Solution() {}
    private static void validate(String a, String b) {
        Objects.requireNonNull(a, "a"); Objects.requireNonNull(b, "b");
        if (a.length() > 2_000 || b.length() > 2_000) throw new IllegalArgumentException("text too long");
    }
    public static int longestCommonSubsequence(String a, String b) {
        validate(a, b);
        String rows = a, columns = b;
        if (columns.length() > rows.length()) { rows = b; columns = a; }
        int[] dp = new int[columns.length() + 1];
        for (int i = 1; i <= rows.length(); i++) {
            int diagonal = 0;
            for (int j = 1; j <= columns.length(); j++) {
                int up = dp[j];
                if (rows.charAt(i - 1) == columns.charAt(j - 1)) dp[j] = diagonal + 1;
                else dp[j] = Math.max(up, dp[j - 1]);
                diagonal = up;
            }
        }
        return dp[columns.length()];
    }
    // Baseline: uncached suffix recursion; restrict execution to short strings.
    public static int baseline(String a, String b) {
        validate(a, b);
        return suffix(a, b, 0, 0);
    }
    private static int suffix(String a, String b, int i, int j) {
        if (i == a.length() || j == b.length()) return 0;
        if (a.charAt(i) == b.charAt(j)) return 1 + suffix(a, b, i + 1, j + 1);
        return Math.max(suffix(a, b, i + 1, j), suffix(a, b, i, j + 1));
    }
}

Read the meaningful blocks

Validate, then select table orientation

The method may swap local string references so the allocated row has min(m,n)+1 entries. This changes neither string content nor the symmetric length objective. It does not copy the text.

Read old up before updating the cell

int up=dp[j] protects the previous row value. The match reads diagonal; the mismatch reads up and current dp[j−1]. The column-zero base remains zero in every row.

Carry the old up into the next diagonal

diagonal=up belongs after the update. Reading dp[j] at that point would carry the new current-row score instead of the required old-row value, possibly reusing a code unit more than once.

Complexity

For m and n code units, the reference takes O(mn+m+n+1) time, including loops on empty-axis cases, and O(min(m,n)+1) auxiliary int storage. Output is one int. Character comparison is constant-time under the UTF-16-unit contract.

The uncached recursive baseline uses O(2^(m+n)) upper-bound time and O(m+n+1) stack space. A full table uses O(mn) space and supports simple traceback. Hirschberg-style divide-and-conquer can reconstruct a sequence with linear score storage, but its output and recursion bookkeeping must be accounted for separately.

Exact-state walkthroughs

Reveal normal and boundary traces

Gaps preserve previous matches

Input: {"a":"abc","b":"ac"} · Common subsequence length: 2

Step 1 of 18: Choose the shorter column axis and initialize empty-prefix boundaries.

Empty-prefix LCS values are zero. The full grid is teaching history; the Java reference retains only one row.

LCS — two-prefix alignment and old/new row dependencies

Phase: initial.

Original inputs: {"a":"abc","b":"ac"}. The shorter string is already in columns. LCS length is symmetric; swapping axes preserves the numeric answer.

Rows: "abc". Columns: "ac". Indices are prefix lengths measured in UTF-16 code units.

Conceptual LCS length grid — ∅ is an empty prefix; · is uncomputed
Row / column	1: "a"	2: "c"
0 — ∅	0	0
1: "a"	·	·
2: "b"	·	·
3: "c"	·	·

Actual one-row Java buffer

dp[0]=0 — boundary/final row
dp[1]=0 — boundary/final row
dp[2]=0 — boundary/final row

Every empty-prefix boundary is zero. Gaps preserve earlier matches; mismatch does not reset a score. The complete grid is explanatory history. Java allocates only the shorter score row and constant temporary values; reconstruction requires additional history.

State after this step
Variable	Value
input	`{"a":"abc","b":"ac"}`
phase	`"initial"`
rows	`"abc"`
columns	`"ac"`
swapped	`false`
table	`[[0,0,0],[0,null,null],[0,null,null],[0,null,null]]`
dp	`[0,0,0]`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     private Solution() {}
 5     private static void validate(String a, String b) {
 6         Objects.requireNonNull(a, "a"); Objects.requireNonNull(b, "b");
 7         if (a.length() > 2_000 || b.length() > 2_000) throw new IllegalArgumentException("text too long");
 8     }
 9     public static int longestCommonSubsequence(String a, String b) {
10         validate(a, b);
11         String rows = a, columns = b;
12         if (columns.length() > rows.length()) { rows = b; columns = a; }
13         int[] dp = new int[columns.length() + 1];
14         for (int i = 1; i <= rows.length(); i++) {
15             int diagonal = 0;
16             for (int j = 1; j <= columns.length(); j++) {
17                 int up = dp[j];
18                 if (rows.charAt(i - 1) == columns.charAt(j - 1)) dp[j] = diagonal + 1;
19                 else dp[j] = Math.max(up, dp[j - 1]);
20                 diagonal = up;
21             }
22         }
23         return dp[columns.length()];
24     }
25     // Baseline: uncached suffix recursion; restrict execution to short strings.
26     public static int baseline(String a, String b) {
27         validate(a, b);
28         return suffix(a, b, 0, 0);
29     }
30     private static int suffix(String a, String b, int i, int j) {
31         if (i == a.length() || j == b.length()) return 0;
32         if (a.charAt(i) == b.charAt(j)) return 1 + suffix(a, b, i + 1, j + 1);
33         return Math.max(suffix(a, b, i + 1, j), suffix(a, b, i, j + 1));
34     }
35 }
36

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Choose the shorter column axis and initialize empty-prefix boundaries.
Empty-prefix LCS values are zero. The full grid is teaching history; the Java reference retains only one row.
input
{"a":"abc","b":"ac"}
phase
"initial"
rows
"abc"
columns
"ac"
swapped
false
table
[[0,0,0],[0,null,null],[0,null,null],[0,null,null]]
dp
[0,0,0]
Prepare the first column and the old diagonal for this row.
The left-to-right update mixes previous-row entries on the right with current-row entries on the left. The saved diagonal must survive until consumed.
input
{"a":"abc","b":"ac"}
phase
"row-start"
rows
"abc"
columns
"ac"
swapped
false
table
[[0,0,0],[0,null,null],[0,null,null],[0,null,null]]
dp
[0,0,0]
i
1
j
0
diagonal
0
Read old up and diagonal together with the current left.
Match adds one to the old diagonal; mismatch maximizes omitting one final unit. New left and old up belong to different row versions.
input
{"a":"abc","b":"ac"}
phase
"candidate"
rows
"abc"
columns
"ac"
swapped
false
table
[[0,0,0],[0,null,null],[0,null,null],[0,null,null]]
dp
[0,0,0]
i
1
j
1
diagonal
0
oldDiagonal
0
up
0
left
0
equal
true
next
1
Write the cell and carry the saved old up as the next diagonal.
oldDiagonal retains the dependency used in this update; live diagonal now carries the old up for the next column. The new dp[j] must not become that next diagonal.
input
{"a":"abc","b":"ac"}
phase
"commit"
rows
"abc"
columns
"ac"
swapped
false
table
[[0,0,0],[0,1,null],[0,null,null],[0,null,null]]
dp
[0,1,0]
i
1
j
1
diagonal
0
oldDiagonal
0
up
0
left
0
equal
true
next
1
Read old up and diagonal together with the current left.
Match adds one to the old diagonal; mismatch maximizes omitting one final unit. New left and old up belong to different row versions.
input
{"a":"abc","b":"ac"}
phase
"candidate"
rows
"abc"
columns
"ac"
swapped
false
table
[[0,0,0],[0,1,null],[0,null,null],[0,null,null]]
dp
[0,1,0]
i
1
j
2
diagonal
0
oldDiagonal
0
up
0
left
1
equal
false
next
1
Write the cell and carry the saved old up as the next diagonal.
oldDiagonal retains the dependency used in this update; live diagonal now carries the old up for the next column. The new dp[j] must not become that next diagonal.
input
{"a":"abc","b":"ac"}
phase
"commit"
rows
"abc"
columns
"ac"
swapped
false
table
[[0,0,0],[0,1,1],[0,null,null],[0,null,null]]
dp
[0,1,1]
i
1
j
2
diagonal
0
oldDiagonal
0
up
0
left
1
equal
false
next
1
Prepare the first column and the old diagonal for this row.
The left-to-right update mixes previous-row entries on the right with current-row entries on the left. The saved diagonal must survive until consumed.
input
{"a":"abc","b":"ac"}
phase
"row-start"
rows
"abc"
columns
"ac"
swapped
false
table
[[0,0,0],[0,1,1],[0,null,null],[0,null,null]]
dp
[0,1,1]
i
2
j
0
diagonal
0
Read old up and diagonal together with the current left.
Match adds one to the old diagonal; mismatch maximizes omitting one final unit. New left and old up belong to different row versions.
input
{"a":"abc","b":"ac"}
phase
"candidate"
rows
"abc"
columns
"ac"
swapped
false
table
[[0,0,0],[0,1,1],[0,null,null],[0,null,null]]
dp
[0,1,1]
i
2
j
1
diagonal
0
oldDiagonal
0
up
1
left
0
equal
false
next
1
Write the cell and carry the saved old up as the next diagonal.
oldDiagonal retains the dependency used in this update; live diagonal now carries the old up for the next column. The new dp[j] must not become that next diagonal.
input
{"a":"abc","b":"ac"}
phase
"commit"
rows
"abc"
columns
"ac"
swapped
false
table
[[0,0,0],[0,1,1],[0,1,null],[0,null,null]]
dp
[0,1,1]
i
2
j
1
diagonal
1
oldDiagonal
0
up
1
left
0
equal
false
next
1
Read old up and diagonal together with the current left.
Match adds one to the old diagonal; mismatch maximizes omitting one final unit. New left and old up belong to different row versions.
input
{"a":"abc","b":"ac"}
phase
"candidate"
rows
"abc"
columns
"ac"
swapped
false
table
[[0,0,0],[0,1,1],[0,1,null],[0,null,null]]
dp
[0,1,1]
i
2
j
2
diagonal
1
oldDiagonal
1
up
1
left
1
equal
false
next
1
Write the cell and carry the saved old up as the next diagonal.
oldDiagonal retains the dependency used in this update; live diagonal now carries the old up for the next column. The new dp[j] must not become that next diagonal.
input
{"a":"abc","b":"ac"}
phase
"commit"
rows
"abc"
columns
"ac"
swapped
false
table
[[0,0,0],[0,1,1],[0,1,1],[0,null,null]]
dp
[0,1,1]
i
2
j
2
diagonal
1
oldDiagonal
1
up
1
left
1
equal
false
next
1
Prepare the first column and the old diagonal for this row.
The left-to-right update mixes previous-row entries on the right with current-row entries on the left. The saved diagonal must survive until consumed.
input
{"a":"abc","b":"ac"}
phase
"row-start"
rows
"abc"
columns
"ac"
swapped
false
table
[[0,0,0],[0,1,1],[0,1,1],[0,null,null]]
dp
[0,1,1]
i
3
j
0
diagonal
0
Read old up and diagonal together with the current left.
Match adds one to the old diagonal; mismatch maximizes omitting one final unit. New left and old up belong to different row versions.
input
{"a":"abc","b":"ac"}
phase
"candidate"
rows
"abc"
columns
"ac"
swapped
false
table
[[0,0,0],[0,1,1],[0,1,1],[0,null,null]]
dp
[0,1,1]
i
3
j
1
diagonal
0
oldDiagonal
0
up
1
left
0
equal
false
next
1
Write the cell and carry the saved old up as the next diagonal.
oldDiagonal retains the dependency used in this update; live diagonal now carries the old up for the next column. The new dp[j] must not become that next diagonal.
input
{"a":"abc","b":"ac"}
phase
"commit"
rows
"abc"
columns
"ac"
swapped
false
table
[[0,0,0],[0,1,1],[0,1,1],[0,1,null]]
dp
[0,1,1]
i
3
j
1
diagonal
1
oldDiagonal
0
up
1
left
0
equal
false
next
1
Read old up and diagonal together with the current left.
Match adds one to the old diagonal; mismatch maximizes omitting one final unit. New left and old up belong to different row versions.
input
{"a":"abc","b":"ac"}
phase
"candidate"
rows
"abc"
columns
"ac"
swapped
false
table
[[0,0,0],[0,1,1],[0,1,1],[0,1,null]]
dp
[0,1,1]
i
3
j
2
diagonal
1
oldDiagonal
1
up
1
left
1
equal
true
next
2
Write the cell and carry the saved old up as the next diagonal.
oldDiagonal retains the dependency used in this update; live diagonal now carries the old up for the next column. The new dp[j] must not become that next diagonal.
input
{"a":"abc","b":"ac"}
phase
"commit"
rows
"abc"
columns
"ac"
swapped
false
table
[[0,0,0],[0,1,1],[0,1,1],[0,1,2]]
dp
[0,1,2]
i
3
j
2
diagonal
1
oldDiagonal
1
up
1
left
1
equal
true
next
2
Return the full-prefix score from the final row.
The numeric length is symmetric under axis swapping. No traceback decisions are retained, so the row is not a subsequence witness.
input
{"a":"abc","b":"ac"}
phase
"complete"
rows
"abc"
columns
"ac"
swapped
false
table
[[0,0,0],[0,1,1],[0,1,1],[0,1,2]]
dp
[0,1,2]
Return the documented result.
Displayed grids, snapshots and saved candidate annotations are teaching history, excluded from the Java implementation workspace. BigInteger counts use exact decimal strings in trace data.
result
2

Order prevents using both common values

Input: {"a":"ab","b":"ba"} · Common subsequence length: 1

Step 1 of 13: Choose the shorter column axis and initialize empty-prefix boundaries.

Empty-prefix LCS values are zero. The full grid is teaching history; the Java reference retains only one row.

LCS — two-prefix alignment and old/new row dependencies

Phase: initial.

Original inputs: {"a":"ab","b":"ba"}. The shorter string is already in columns. LCS length is symmetric; swapping axes preserves the numeric answer.

Rows: "ab". Columns: "ba". Indices are prefix lengths measured in UTF-16 code units.

Conceptual LCS length grid — ∅ is an empty prefix; · is uncomputed
Row / column	1: "b"	2: "a"
0 — ∅	0	0
1: "a"	·	·
2: "b"	·	·

Actual one-row Java buffer

dp[0]=0 — boundary/final row
dp[1]=0 — boundary/final row
dp[2]=0 — boundary/final row

State after this step
Variable	Value
input	`{"a":"ab","b":"ba"}`
phase	`"initial"`
rows	`"ab"`
columns	`"ba"`
swapped	`false`
table	`[[0,0,0],[0,null,null],[0,null,null]]`
dp	`[0,0,0]`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     private Solution() {}
 5     private static void validate(String a, String b) {
 6         Objects.requireNonNull(a, "a"); Objects.requireNonNull(b, "b");
 7         if (a.length() > 2_000 || b.length() > 2_000) throw new IllegalArgumentException("text too long");
 8     }
 9     public static int longestCommonSubsequence(String a, String b) {
10         validate(a, b);
11         String rows = a, columns = b;
12         if (columns.length() > rows.length()) { rows = b; columns = a; }
13         int[] dp = new int[columns.length() + 1];
14         for (int i = 1; i <= rows.length(); i++) {
15             int diagonal = 0;
16             for (int j = 1; j <= columns.length(); j++) {
17                 int up = dp[j];
18                 if (rows.charAt(i - 1) == columns.charAt(j - 1)) dp[j] = diagonal + 1;
19                 else dp[j] = Math.max(up, dp[j - 1]);
20                 diagonal = up;
21             }
22         }
23         return dp[columns.length()];
24     }
25     // Baseline: uncached suffix recursion; restrict execution to short strings.
26     public static int baseline(String a, String b) {
27         validate(a, b);
28         return suffix(a, b, 0, 0);
29     }
30     private static int suffix(String a, String b, int i, int j) {
31         if (i == a.length() || j == b.length()) return 0;
32         if (a.charAt(i) == b.charAt(j)) return 1 + suffix(a, b, i + 1, j + 1);
33         return Math.max(suffix(a, b, i + 1, j), suffix(a, b, i, j + 1));
34     }
35 }
36

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Choose the shorter column axis and initialize empty-prefix boundaries.
Empty-prefix LCS values are zero. The full grid is teaching history; the Java reference retains only one row.
input
{"a":"ab","b":"ba"}
phase
"initial"
rows
"ab"
columns
"ba"
swapped
false
table
[[0,0,0],[0,null,null],[0,null,null]]
dp
[0,0,0]
Prepare the first column and the old diagonal for this row.
The left-to-right update mixes previous-row entries on the right with current-row entries on the left. The saved diagonal must survive until consumed.
input
{"a":"ab","b":"ba"}
phase
"row-start"
rows
"ab"
columns
"ba"
swapped
false
table
[[0,0,0],[0,null,null],[0,null,null]]
dp
[0,0,0]
i
1
j
0
diagonal
0
Read old up and diagonal together with the current left.
Match adds one to the old diagonal; mismatch maximizes omitting one final unit. New left and old up belong to different row versions.
input
{"a":"ab","b":"ba"}
phase
"candidate"
rows
"ab"
columns
"ba"
swapped
false
table
[[0,0,0],[0,null,null],[0,null,null]]
dp
[0,0,0]
i
1
j
1
diagonal
0
oldDiagonal
0
up
0
left
0
equal
false
next
0
Write the cell and carry the saved old up as the next diagonal.
oldDiagonal retains the dependency used in this update; live diagonal now carries the old up for the next column. The new dp[j] must not become that next diagonal.
input
{"a":"ab","b":"ba"}
phase
"commit"
rows
"ab"
columns
"ba"
swapped
false
table
[[0,0,0],[0,0,null],[0,null,null]]
dp
[0,0,0]
i
1
j
1
diagonal
0
oldDiagonal
0
up
0
left
0
equal
false
next
0
Read old up and diagonal together with the current left.
Match adds one to the old diagonal; mismatch maximizes omitting one final unit. New left and old up belong to different row versions.
input
{"a":"ab","b":"ba"}
phase
"candidate"
rows
"ab"
columns
"ba"
swapped
false
table
[[0,0,0],[0,0,null],[0,null,null]]
dp
[0,0,0]
i
1
j
2
diagonal
0
oldDiagonal
0
up
0
left
0
equal
true
next
1
Write the cell and carry the saved old up as the next diagonal.
oldDiagonal retains the dependency used in this update; live diagonal now carries the old up for the next column. The new dp[j] must not become that next diagonal.
input
{"a":"ab","b":"ba"}
phase
"commit"
rows
"ab"
columns
"ba"
swapped
false
table
[[0,0,0],[0,0,1],[0,null,null]]
dp
[0,0,1]
i
1
j
2
diagonal
0
oldDiagonal
0
up
0
left
0
equal
true
next
1
Prepare the first column and the old diagonal for this row.
The left-to-right update mixes previous-row entries on the right with current-row entries on the left. The saved diagonal must survive until consumed.
input
{"a":"ab","b":"ba"}
phase
"row-start"
rows
"ab"
columns
"ba"
swapped
false
table
[[0,0,0],[0,0,1],[0,null,null]]
dp
[0,0,1]
i
2
j
0
diagonal
0
Read old up and diagonal together with the current left.
Match adds one to the old diagonal; mismatch maximizes omitting one final unit. New left and old up belong to different row versions.
input
{"a":"ab","b":"ba"}
phase
"candidate"
rows
"ab"
columns
"ba"
swapped
false
table
[[0,0,0],[0,0,1],[0,null,null]]
dp
[0,0,1]
i
2
j
1
diagonal
0
oldDiagonal
0
up
0
left
0
equal
true
next
1
Write the cell and carry the saved old up as the next diagonal.
oldDiagonal retains the dependency used in this update; live diagonal now carries the old up for the next column. The new dp[j] must not become that next diagonal.
input
{"a":"ab","b":"ba"}
phase
"commit"
rows
"ab"
columns
"ba"
swapped
false
table
[[0,0,0],[0,0,1],[0,1,null]]
dp
[0,1,1]
i
2
j
1
diagonal
0
oldDiagonal
0
up
0
left
0
equal
true
next
1
Read old up and diagonal together with the current left.
Match adds one to the old diagonal; mismatch maximizes omitting one final unit. New left and old up belong to different row versions.
input
{"a":"ab","b":"ba"}
phase
"candidate"
rows
"ab"
columns
"ba"
swapped
false
table
[[0,0,0],[0,0,1],[0,1,null]]
dp
[0,1,1]
i
2
j
2
diagonal
0
oldDiagonal
0
up
1
left
1
equal
false
next
1
Write the cell and carry the saved old up as the next diagonal.
oldDiagonal retains the dependency used in this update; live diagonal now carries the old up for the next column. The new dp[j] must not become that next diagonal.
input
{"a":"ab","b":"ba"}
phase
"commit"
rows
"ab"
columns
"ba"
swapped
false
table
[[0,0,0],[0,0,1],[0,1,1]]
dp
[0,1,1]
i
2
j
2
diagonal
1
oldDiagonal
0
up
1
left
1
equal
false
next
1
Return the full-prefix score from the final row.
The numeric length is symmetric under axis swapping. No traceback decisions are retained, so the row is not a subsequence witness.
input
{"a":"ab","b":"ba"}
phase
"complete"
rows
"ab"
columns
"ba"
swapped
false
table
[[0,0,0],[0,0,1],[0,1,1]]
dp
[0,1,1]
Return the documented result.
Displayed grids, snapshots and saved candidate annotations are teaching history, excluded from the Java implementation workspace. BigInteger counts use exact decimal strings in trace data.
result
1

Empty column axis

Input: {"a":"abc","b":""} · Common subsequence length: 0

Step 1 of 6: Choose the shorter column axis and initialize empty-prefix boundaries.

Empty-prefix LCS values are zero. The full grid is teaching history; the Java reference retains only one row.

LCS — two-prefix alignment and old/new row dependencies

Phase: initial.

Original inputs: {"a":"abc","b":""}. The shorter string is already in columns. LCS length is symmetric; swapping axes preserves the numeric answer.

Rows: "abc". Columns: "". Indices are prefix lengths measured in UTF-16 code units.

Conceptual LCS length grid — ∅ is an empty prefix; · is uncomputed
Row / column	0 — ∅
0 — ∅	0
1: "a"	0
2: "b"	0
3: "c"	0

Actual one-row Java buffer

dp[0]=0 — boundary/final row

State after this step
Variable	Value
input	`{"a":"abc","b":""}`
phase	`"initial"`
rows	`"abc"`
columns	`""`
swapped	`false`
table	`[[0],[0],[0],[0]]`
dp	`[0]`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     private Solution() {}
 5     private static void validate(String a, String b) {
 6         Objects.requireNonNull(a, "a"); Objects.requireNonNull(b, "b");
 7         if (a.length() > 2_000 || b.length() > 2_000) throw new IllegalArgumentException("text too long");
 8     }
 9     public static int longestCommonSubsequence(String a, String b) {
10         validate(a, b);
11         String rows = a, columns = b;
12         if (columns.length() > rows.length()) { rows = b; columns = a; }
13         int[] dp = new int[columns.length() + 1];
14         for (int i = 1; i <= rows.length(); i++) {
15             int diagonal = 0;
16             for (int j = 1; j <= columns.length(); j++) {
17                 int up = dp[j];
18                 if (rows.charAt(i - 1) == columns.charAt(j - 1)) dp[j] = diagonal + 1;
19                 else dp[j] = Math.max(up, dp[j - 1]);
20                 diagonal = up;
21             }
22         }
23         return dp[columns.length()];
24     }
25     // Baseline: uncached suffix recursion; restrict execution to short strings.
26     public static int baseline(String a, String b) {
27         validate(a, b);
28         return suffix(a, b, 0, 0);
29     }
30     private static int suffix(String a, String b, int i, int j) {
31         if (i == a.length() || j == b.length()) return 0;
32         if (a.charAt(i) == b.charAt(j)) return 1 + suffix(a, b, i + 1, j + 1);
33         return Math.max(suffix(a, b, i + 1, j), suffix(a, b, i, j + 1));
34     }
35 }
36

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Choose the shorter column axis and initialize empty-prefix boundaries.
Empty-prefix LCS values are zero. The full grid is teaching history; the Java reference retains only one row.
input
{"a":"abc","b":""}
phase
"initial"
rows
"abc"
columns
""
swapped
false
table
[[0],[0],[0],[0]]
dp
[0]
Prepare the first column and the old diagonal for this row.
The left-to-right update mixes previous-row entries on the right with current-row entries on the left. The saved diagonal must survive until consumed.
input
{"a":"abc","b":""}
phase
"row-start"
rows
"abc"
columns
""
swapped
false
table
[[0],[0],[0],[0]]
dp
[0]
i
1
j
0
diagonal
0
Prepare the first column and the old diagonal for this row.
The left-to-right update mixes previous-row entries on the right with current-row entries on the left. The saved diagonal must survive until consumed.
input
{"a":"abc","b":""}
phase
"row-start"
rows
"abc"
columns
""
swapped
false
table
[[0],[0],[0],[0]]
dp
[0]
i
2
j
0
diagonal
0
Prepare the first column and the old diagonal for this row.
The left-to-right update mixes previous-row entries on the right with current-row entries on the left. The saved diagonal must survive until consumed.
input
{"a":"abc","b":""}
phase
"row-start"
rows
"abc"
columns
""
swapped
false
table
[[0],[0],[0],[0]]
dp
[0]
i
3
j
0
diagonal
0
Return the full-prefix score from the final row.
The numeric length is symmetric under axis swapping. No traceback decisions are retained, so the row is not a subsequence witness.
input
{"a":"abc","b":""}
phase
"complete"
rows
"abc"
columns
""
swapped
false
table
[[0],[0],[0],[0]]
dp
[0]
Return the documented result.
Displayed grids, snapshots and saved candidate annotations are teaching history, excluded from the Java implementation workspace. BigInteger counts use exact decimal strings in trace data.
result
0

Shorter input becomes columns

Input: {"a":"a","b":"ba"} · Common subsequence length: 1

Step 1 of 9: Choose the shorter column axis and initialize empty-prefix boundaries.

Empty-prefix LCS values are zero. The full grid is teaching history; the Java reference retains only one row.

LCS — two-prefix alignment and old/new row dependencies

Phase: initial.

Original inputs: {"a":"a","b":"ba"}. Axes are swapped to keep the shorter string in columns. LCS length is symmetric; swapping axes preserves the numeric answer.

Rows: "ba". Columns: "a". Indices are prefix lengths measured in UTF-16 code units.

Conceptual LCS length grid — ∅ is an empty prefix; · is uncomputed
Row / column	0 — ∅	1: "a"
0 — ∅	0	0
1: "b"	0	·
2: "a"	0	·

Actual one-row Java buffer

dp[0]=0 — boundary/final row
dp[1]=0 — boundary/final row

State after this step
Variable	Value
input	`{"a":"a","b":"ba"}`
phase	`"initial"`
rows	`"ba"`
columns	`"a"`
swapped	`true`
table	`[[0,0],[0,null],[0,null]]`
dp	`[0,0]`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     private Solution() {}
 5     private static void validate(String a, String b) {
 6         Objects.requireNonNull(a, "a"); Objects.requireNonNull(b, "b");
 7         if (a.length() > 2_000 || b.length() > 2_000) throw new IllegalArgumentException("text too long");
 8     }
 9     public static int longestCommonSubsequence(String a, String b) {
10         validate(a, b);
11         String rows = a, columns = b;
12         if (columns.length() > rows.length()) { rows = b; columns = a; }
13         int[] dp = new int[columns.length() + 1];
14         for (int i = 1; i <= rows.length(); i++) {
15             int diagonal = 0;
16             for (int j = 1; j <= columns.length(); j++) {
17                 int up = dp[j];
18                 if (rows.charAt(i - 1) == columns.charAt(j - 1)) dp[j] = diagonal + 1;
19                 else dp[j] = Math.max(up, dp[j - 1]);
20                 diagonal = up;
21             }
22         }
23         return dp[columns.length()];
24     }
25     // Baseline: uncached suffix recursion; restrict execution to short strings.
26     public static int baseline(String a, String b) {
27         validate(a, b);
28         return suffix(a, b, 0, 0);
29     }
30     private static int suffix(String a, String b, int i, int j) {
31         if (i == a.length() || j == b.length()) return 0;
32         if (a.charAt(i) == b.charAt(j)) return 1 + suffix(a, b, i + 1, j + 1);
33         return Math.max(suffix(a, b, i + 1, j), suffix(a, b, i, j + 1));
34     }
35 }
36

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Choose the shorter column axis and initialize empty-prefix boundaries.
Empty-prefix LCS values are zero. The full grid is teaching history; the Java reference retains only one row.
input
{"a":"a","b":"ba"}
phase
"initial"
rows
"ba"
columns
"a"
swapped
true
table
[[0,0],[0,null],[0,null]]
dp
[0,0]
Prepare the first column and the old diagonal for this row.
The left-to-right update mixes previous-row entries on the right with current-row entries on the left. The saved diagonal must survive until consumed.
input
{"a":"a","b":"ba"}
phase
"row-start"
rows
"ba"
columns
"a"
swapped
true
table
[[0,0],[0,null],[0,null]]
dp
[0,0]
i
1
j
0
diagonal
0
Read old up and diagonal together with the current left.
Match adds one to the old diagonal; mismatch maximizes omitting one final unit. New left and old up belong to different row versions.
input
{"a":"a","b":"ba"}
phase
"candidate"
rows
"ba"
columns
"a"
swapped
true
table
[[0,0],[0,null],[0,null]]
dp
[0,0]
i
1
j
1
diagonal
0
oldDiagonal
0
up
0
left
0
equal
false
next
0
Write the cell and carry the saved old up as the next diagonal.
oldDiagonal retains the dependency used in this update; live diagonal now carries the old up for the next column. The new dp[j] must not become that next diagonal.
input
{"a":"a","b":"ba"}
phase
"commit"
rows
"ba"
columns
"a"
swapped
true
table
[[0,0],[0,0],[0,null]]
dp
[0,0]
i
1
j
1
diagonal
0
oldDiagonal
0
up
0
left
0
equal
false
next
0
Prepare the first column and the old diagonal for this row.
The left-to-right update mixes previous-row entries on the right with current-row entries on the left. The saved diagonal must survive until consumed.
input
{"a":"a","b":"ba"}
phase
"row-start"
rows
"ba"
columns
"a"
swapped
true
table
[[0,0],[0,0],[0,null]]
dp
[0,0]
i
2
j
0
diagonal
0
Read old up and diagonal together with the current left.
Match adds one to the old diagonal; mismatch maximizes omitting one final unit. New left and old up belong to different row versions.
input
{"a":"a","b":"ba"}
phase
"candidate"
rows
"ba"
columns
"a"
swapped
true
table
[[0,0],[0,0],[0,null]]
dp
[0,0]
i
2
j
1
diagonal
0
oldDiagonal
0
up
0
left
0
equal
true
next
1
Write the cell and carry the saved old up as the next diagonal.
oldDiagonal retains the dependency used in this update; live diagonal now carries the old up for the next column. The new dp[j] must not become that next diagonal.
input
{"a":"a","b":"ba"}
phase
"commit"
rows
"ba"
columns
"a"
swapped
true
table
[[0,0],[0,0],[0,1]]
dp
[0,1]
i
2
j
1
diagonal
0
oldDiagonal
0
up
0
left
0
equal
true
next
1
Return the full-prefix score from the final row.
The numeric length is symmetric under axis swapping. No traceback decisions are retained, so the row is not a subsequence witness.
input
{"a":"a","b":"ba"}
phase
"complete"
rows
"ba"
columns
"a"
swapped
true
table
[[0,0],[0,0],[0,1]]
dp
[0,1]
Return the documented result.
Displayed grids, snapshots and saved candidate annotations are teaching history, excluded from the Java implementation workspace. BigInteger counts use exact decimal strings in trace data.
result
1

Repeated units have separate occurrences

Input: {"a":"aaa","b":"aa"} · Common subsequence length: 2

Step 1 of 18: Choose the shorter column axis and initialize empty-prefix boundaries.

Empty-prefix LCS values are zero. The full grid is teaching history; the Java reference retains only one row.

LCS — two-prefix alignment and old/new row dependencies

Phase: initial.

Original inputs: {"a":"aaa","b":"aa"}. The shorter string is already in columns. LCS length is symmetric; swapping axes preserves the numeric answer.

Rows: "aaa". Columns: "aa". Indices are prefix lengths measured in UTF-16 code units.

Conceptual LCS length grid — ∅ is an empty prefix; · is uncomputed
Row / column	1: "a"	2: "a"
0 — ∅	0	0
1: "a"	·	·
2: "a"	·	·
3: "a"	·	·

Actual one-row Java buffer

dp[0]=0 — boundary/final row
dp[1]=0 — boundary/final row
dp[2]=0 — boundary/final row

State after this step
Variable	Value
input	`{"a":"aaa","b":"aa"}`
phase	`"initial"`
rows	`"aaa"`
columns	`"aa"`
swapped	`false`
table	`[[0,0,0],[0,null,null],[0,null,null],[0,null,null]]`
dp	`[0,0,0]`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     private Solution() {}
 5     private static void validate(String a, String b) {
 6         Objects.requireNonNull(a, "a"); Objects.requireNonNull(b, "b");
 7         if (a.length() > 2_000 || b.length() > 2_000) throw new IllegalArgumentException("text too long");
 8     }
 9     public static int longestCommonSubsequence(String a, String b) {
10         validate(a, b);
11         String rows = a, columns = b;
12         if (columns.length() > rows.length()) { rows = b; columns = a; }
13         int[] dp = new int[columns.length() + 1];
14         for (int i = 1; i <= rows.length(); i++) {
15             int diagonal = 0;
16             for (int j = 1; j <= columns.length(); j++) {
17                 int up = dp[j];
18                 if (rows.charAt(i - 1) == columns.charAt(j - 1)) dp[j] = diagonal + 1;
19                 else dp[j] = Math.max(up, dp[j - 1]);
20                 diagonal = up;
21             }
22         }
23         return dp[columns.length()];
24     }
25     // Baseline: uncached suffix recursion; restrict execution to short strings.
26     public static int baseline(String a, String b) {
27         validate(a, b);
28         return suffix(a, b, 0, 0);
29     }
30     private static int suffix(String a, String b, int i, int j) {
31         if (i == a.length() || j == b.length()) return 0;
32         if (a.charAt(i) == b.charAt(j)) return 1 + suffix(a, b, i + 1, j + 1);
33         return Math.max(suffix(a, b, i + 1, j), suffix(a, b, i, j + 1));
34     }
35 }
36

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Choose the shorter column axis and initialize empty-prefix boundaries.
Empty-prefix LCS values are zero. The full grid is teaching history; the Java reference retains only one row.
input
{"a":"aaa","b":"aa"}
phase
"initial"
rows
"aaa"
columns
"aa"
swapped
false
table
[[0,0,0],[0,null,null],[0,null,null],[0,null,null]]
dp
[0,0,0]
Prepare the first column and the old diagonal for this row.
The left-to-right update mixes previous-row entries on the right with current-row entries on the left. The saved diagonal must survive until consumed.
input
{"a":"aaa","b":"aa"}
phase
"row-start"
rows
"aaa"
columns
"aa"
swapped
false
table
[[0,0,0],[0,null,null],[0,null,null],[0,null,null]]
dp
[0,0,0]
i
1
j
0
diagonal
0
Read old up and diagonal together with the current left.
Match adds one to the old diagonal; mismatch maximizes omitting one final unit. New left and old up belong to different row versions.
input
{"a":"aaa","b":"aa"}
phase
"candidate"
rows
"aaa"
columns
"aa"
swapped
false
table
[[0,0,0],[0,null,null],[0,null,null],[0,null,null]]
dp
[0,0,0]
i
1
j
1
diagonal
0
oldDiagonal
0
up
0
left
0
equal
true
next
1
Write the cell and carry the saved old up as the next diagonal.
oldDiagonal retains the dependency used in this update; live diagonal now carries the old up for the next column. The new dp[j] must not become that next diagonal.
input
{"a":"aaa","b":"aa"}
phase
"commit"
rows
"aaa"
columns
"aa"
swapped
false
table
[[0,0,0],[0,1,null],[0,null,null],[0,null,null]]
dp
[0,1,0]
i
1
j
1
diagonal
0
oldDiagonal
0
up
0
left
0
equal
true
next
1
Read old up and diagonal together with the current left.
Match adds one to the old diagonal; mismatch maximizes omitting one final unit. New left and old up belong to different row versions.
input
{"a":"aaa","b":"aa"}
phase
"candidate"
rows
"aaa"
columns
"aa"
swapped
false
table
[[0,0,0],[0,1,null],[0,null,null],[0,null,null]]
dp
[0,1,0]
i
1
j
2
diagonal
0
oldDiagonal
0
up
0
left
1
equal
true
next
1
Write the cell and carry the saved old up as the next diagonal.
oldDiagonal retains the dependency used in this update; live diagonal now carries the old up for the next column. The new dp[j] must not become that next diagonal.
input
{"a":"aaa","b":"aa"}
phase
"commit"
rows
"aaa"
columns
"aa"
swapped
false
table
[[0,0,0],[0,1,1],[0,null,null],[0,null,null]]
dp
[0,1,1]
i
1
j
2
diagonal
0
oldDiagonal
0
up
0
left
1
equal
true
next
1
Prepare the first column and the old diagonal for this row.
The left-to-right update mixes previous-row entries on the right with current-row entries on the left. The saved diagonal must survive until consumed.
input
{"a":"aaa","b":"aa"}
phase
"row-start"
rows
"aaa"
columns
"aa"
swapped
false
table
[[0,0,0],[0,1,1],[0,null,null],[0,null,null]]
dp
[0,1,1]
i
2
j
0
diagonal
0
Read old up and diagonal together with the current left.
Match adds one to the old diagonal; mismatch maximizes omitting one final unit. New left and old up belong to different row versions.
input
{"a":"aaa","b":"aa"}
phase
"candidate"
rows
"aaa"
columns
"aa"
swapped
false
table
[[0,0,0],[0,1,1],[0,null,null],[0,null,null]]
dp
[0,1,1]
i
2
j
1
diagonal
0
oldDiagonal
0
up
1
left
0
equal
true
next
1
Write the cell and carry the saved old up as the next diagonal.
oldDiagonal retains the dependency used in this update; live diagonal now carries the old up for the next column. The new dp[j] must not become that next diagonal.
input
{"a":"aaa","b":"aa"}
phase
"commit"
rows
"aaa"
columns
"aa"
swapped
false
table
[[0,0,0],[0,1,1],[0,1,null],[0,null,null]]
dp
[0,1,1]
i
2
j
1
diagonal
1
oldDiagonal
0
up
1
left
0
equal
true
next
1
Read old up and diagonal together with the current left.
Match adds one to the old diagonal; mismatch maximizes omitting one final unit. New left and old up belong to different row versions.
input
{"a":"aaa","b":"aa"}
phase
"candidate"
rows
"aaa"
columns
"aa"
swapped
false
table
[[0,0,0],[0,1,1],[0,1,null],[0,null,null]]
dp
[0,1,1]
i
2
j
2
diagonal
1
oldDiagonal
1
up
1
left
1
equal
true
next
2
Write the cell and carry the saved old up as the next diagonal.
oldDiagonal retains the dependency used in this update; live diagonal now carries the old up for the next column. The new dp[j] must not become that next diagonal.
input
{"a":"aaa","b":"aa"}
phase
"commit"
rows
"aaa"
columns
"aa"
swapped
false
table
[[0,0,0],[0,1,1],[0,1,2],[0,null,null]]
dp
[0,1,2]
i
2
j
2
diagonal
1
oldDiagonal
1
up
1
left
1
equal
true
next
2
Prepare the first column and the old diagonal for this row.
The left-to-right update mixes previous-row entries on the right with current-row entries on the left. The saved diagonal must survive until consumed.
input
{"a":"aaa","b":"aa"}
phase
"row-start"
rows
"aaa"
columns
"aa"
swapped
false
table
[[0,0,0],[0,1,1],[0,1,2],[0,null,null]]
dp
[0,1,2]
i
3
j
0
diagonal
0
Read old up and diagonal together with the current left.
Match adds one to the old diagonal; mismatch maximizes omitting one final unit. New left and old up belong to different row versions.
input
{"a":"aaa","b":"aa"}
phase
"candidate"
rows
"aaa"
columns
"aa"
swapped
false
table
[[0,0,0],[0,1,1],[0,1,2],[0,null,null]]
dp
[0,1,2]
i
3
j
1
diagonal
0
oldDiagonal
0
up
1
left
0
equal
true
next
1
Write the cell and carry the saved old up as the next diagonal.
oldDiagonal retains the dependency used in this update; live diagonal now carries the old up for the next column. The new dp[j] must not become that next diagonal.
input
{"a":"aaa","b":"aa"}
phase
"commit"
rows
"aaa"
columns
"aa"
swapped
false
table
[[0,0,0],[0,1,1],[0,1,2],[0,1,null]]
dp
[0,1,2]
i
3
j
1
diagonal
1
oldDiagonal
0
up
1
left
0
equal
true
next
1
Read old up and diagonal together with the current left.
Match adds one to the old diagonal; mismatch maximizes omitting one final unit. New left and old up belong to different row versions.
input
{"a":"aaa","b":"aa"}
phase
"candidate"
rows
"aaa"
columns
"aa"
swapped
false
table
[[0,0,0],[0,1,1],[0,1,2],[0,1,null]]
dp
[0,1,2]
i
3
j
2
diagonal
1
oldDiagonal
1
up
2
left
1
equal
true
next
2
Write the cell and carry the saved old up as the next diagonal.
oldDiagonal retains the dependency used in this update; live diagonal now carries the old up for the next column. The new dp[j] must not become that next diagonal.
input
{"a":"aaa","b":"aa"}
phase
"commit"
rows
"aaa"
columns
"aa"
swapped
false
table
[[0,0,0],[0,1,1],[0,1,2],[0,1,2]]
dp
[0,1,2]
i
3
j
2
diagonal
2
oldDiagonal
1
up
2
left
1
equal
true
next
2
Return the full-prefix score from the final row.
The numeric length is symmetric under axis swapping. No traceback decisions are retained, so the row is not a subsequence witness.
input
{"a":"aaa","b":"aa"}
phase
"complete"
rows
"aaa"
columns
"aa"
swapped
false
table
[[0,0,0],[0,1,1],[0,1,2],[0,1,2]]
dp
[0,1,2]
Return the documented result.
Displayed grids, snapshots and saved candidate annotations are teaching history, excluded from the Java implementation workspace. BigInteger counts use exact decimal strings in trace data.
result
2

Test the contract

Input: a="", b="abc"
Output: 0
Empty-prefix base.
Input: a="aaaa", b="aa"
Output: 2
Repeated values cannot reuse an occurrence.
Input: a="ABC", b="abc"
Output: 0
Exact case-sensitive matching.
Input: a="αβ", b="β"
Output: 1
Unicode BMP matching.
Input: a="abc", b="abc"
Output: 3
All occurrences can pair.
Input: a=null, b=""
Output: NullPointerException
Validate before empty shortcuts.

Common mistakes and counterexamples

Require matching units to be adjacent

Counterexample: abcde and ace have LCS length three despite the gaps.

Preserve order while allowing omissions; do not apply a substring recurrence.

Count common characters without ordering

Counterexample: ab and ba share two values but have LCS length one.

Use a state for both prefix positions.

Reset on mismatch

Counterexample: The b row in abc versus ac retains the earlier a match.

Carry the maximum of omitting a final unit from either side.

Overwrite the saved diagonal or promise tails-like reconstruction

Counterexample: Using the newly written score as diagonal can reuse matches; a single final row has lost traceback choices.

Save old up first, advance diagonal afterward, and store explicit reconstruction history if needed.

Follow-ups

Return one longest common subsequence.

Keep a full score table and trace backward, taking a matching diagonal or an optimum-preserving omission. Specify deterministic choices on ties. Output source indices if equal-looking values need identity; a returned string alone does not identify which occurrences were used.

Reduce memory while reconstructing.

Use divide-and-conquer with forward and backward score rows to choose a split in one string, then recursively reconstruct each half. Explain the split optimality and avoid retaining all recursion-level score buffers simultaneously. Linear score workspace does not make output free.

Relate LCS to insertion/deletion distance.

When only insertions and deletions are allowed, the minimum cost is m+n−2LCS: keep a maximum common subsequence and delete/insert everything else. With unit-cost substitutions this identity no longer gives Levenshtein distance; changing a to b takes one substitution although the expression gives two.

Related foundations

Dynamic programming: state before recurrence

Keep practicing

Return to the lesson

AceYourInterviews · 2026-10-17 · Original teaching content and implementations authored for AceYourInterviews. Familiar interview problem names describe standard algorithmic tasks; no company-frequency or platform-difficulty claims are made.