Java edit distance: two rows and a declared text unit

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

State what a sequence element means

This implementation treats each UTF-16 code unit as an element. That is a deliberate algorithm contract, not a claim about user-perceived characters. A text-correction feature working on grapheme clusters needs to segment first and then apply a corresponding sequence algorithm.

Each cell depends on a deletion, insertion or substitution from neighboring states. Only the previous row and the current row are needed for the final distance, so the implementation avoids retaining the complete matrix. It swaps the input references so the row width follows the shorter input.

The row reduction cannot reconstruct an edit script by itself. If the UI needs highlighted edits, retain predecessor information or use an algorithm that reconstructs the path with its own storage policy. A scalar distance alone does not identify which positions should be changed.

Use a work budget

Even with two rows, the operation still performs a product of the sequence lengths. The fixture rejects more than four million cell updates. That budget keeps this tutorial program bounded; an online endpoint needs a timeout and admission policy as well as an input length rule.

Working program

public class ReceiptLabelDistance {
    static int distance(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("Distance work budget");
        if(a.length()<b.length()){String swap=a;a=b;b=swap;}
        int[] previous=new int[b.length()+1],current=new int[b.length()+1];for(int j=0;j<previous.length;j++)previous[j]=j;
        for(int i=1;i<=a.length();i++){
            current[0]=i;for(int j=1;j<=b.length();j++)current[j]=Math.min(Math.min(previous[j]+1,current[j-1]+1),previous[j-1]+(a.charAt(i-1)==b.charAt(j-1)?0:1));
            int[] swap=previous;previous=current;current=swap;
        }return previous[b.length()];
    }
    public static void main(String[] args){System.out.println(distance("parcel","parcels"));System.out.println(distance("label","table"));System.out.println(distance("","PK"));}
}

Output

1
3
2

Costs and boundaries

Time is O(mn), and auxiliary row storage is O(min(m,n)). Empty-input handling still needs linear row initialization or traversal under this implementation. UTF-16 distance can differ from code-point or grapheme-cluster distance.

Common Mistakes

• Two-row storage does not automatically provide an edit script.
• A smaller memory footprint does not reduce quadratic work.
• Specify the text unit before interpreting the score.

Read next

Display units, State dependency order.