Choose the edit operations explicitly
Here Levenshtein distance assigns unit cost to inserting, deleting or substituting one character, and zero cost to aligning equal characters. Swapping adjacent characters is not a primitive operation in this model. Allowing such a swap defines a different edit-distance variant. Changing allowed operations or costs can change the result, so similarity is not a complete specification. For example, transforming ab into ba costs two substitutions under this model, rather than one adjacent swap. A small character-edit distance also does not establish that two strings have similar meanings or represent the same entity.
Build the table over prefixes
Let D[i][j] be the minimum cost of converting the first i source characters into the first j target characters. Set D[i][0]=i and D[0][j]=j. Each internal cell takes the minimum of deletion D[i−1][j]+1, insertion D[i][j−1]+1, and alignment D[i−1][j−1]+c, where c is zero for equal characters and one otherwise. These cases classify the final operation of a valid edit sequence. Fill the table in an order that makes the upper, left and upper-left dependencies available before the current cell is evaluated.
Trace kitten to sitting
Replace k with s in kitten to get sitten, replace e with i to get sittin, and insert g at the end to get sitting. The total cost is three, matching the dynamic-programming minimum. Counting differing characters at fixed positions would not generally work, because an insertion changes subsequent alignment positions. To reconstruct an actual optimal sequence, backtrack from the final cell through predecessor choices attaining its minimum. Several choices can tie, so a unique distance need not imply a unique optimal alignment. An API returning the distance and one returning edits provide different information.
Trade memory against reconstruction information
The full m-by-n table costs O(mn) time and O(mn) space. If only the distance is needed, retaining the previous and current rows reduces auxiliary storage to O(min(m,n)), but does not retain a complete ordinary backtracking table. Swapping the row and column strings relies on the relevant cost symmetry and should not be copied blindly to unequal-cost variants. Unicode code points are not always user-perceived characters, and normalization choices can affect results. Test empty strings, equal strings, insertion-only examples and adjacent swaps to confirm both the recurrence and the intended character model.