Java longest common subsequence: ordering without contiguity

Java 8+. The program uses JDK classes and requires no preview flags.

Do not substitute substring reasoning

Two versioned manifests can share an ordered sequence of reference characters even when one contains extra characters between them. A substring operation requires contiguity and answers a different question. This implementation returns a length only, making that distinction explicit.

On a match, the current length comes from the previous diagonal plus one. On a mismatch, it comes from the larger of skipping one position in either sequence. Before updating a cell in place, save its old value because the next position still needs that prior-row diagonal.

The implementation uses one row and a diagonal temporary value. That preserves the recurrence while reducing storage. It does not return the matched positions or sequence. A diff view needs a reconstruction strategy and must decide how ties are broken.

Keep comparisons literal

The fixture compares UTF-16 code units exactly. It does not normalize, ignore case or apply locale collation. Those transformations change the sequence and can change the answer, so apply them only under an explicit field policy before running the algorithm.

Working program

public class ManifestCommonOrder {
    static int length(String a,String b){
        java.util.Objects.requireNonNull(a);java.util.Objects.requireNonNull(b);
        if((long)a.length()*b.length()>4_000_000)throw new IllegalArgumentException("Subsequence work budget");
        if(a.length()<b.length()){String swap=a;a=b;b=swap;}int[] row=new int[b.length()+1];
        for(int i=0;i<a.length();i++){
            int diagonal=0;
            for(int j=1;j<row.length;j++){int old=row[j];row[j]=a.charAt(i)==b.charAt(j-1)?diagonal+1:Math.max(row[j],row[j-1]);diagonal=old;}
        }return row[b.length()];
    }
    public static void main(String[] args){System.out.println(length("PKRSL","PRL"));System.out.println(length("ABC","XYZ"));System.out.println(length("","PK"));}
}

Output

3
0
0

Costs and boundaries

Time is O(mn); working storage is O(min(m,n)). The returned length is not a set intersection count and not a contiguous match length. The checked work budget does not turn the algorithm into a real-time service contract.

Common Mistakes

• Keep the previous diagonal before overwriting a row entry.
• A subsequence need not be contiguous.
• Length-only state cannot identify the chosen matching positions.

Read next

Another sequence recurrence, Contiguous matching.