Given 2 sequence A, B (Every char is in {a-z to A-Z})
(length could be different)
You can do 3 manipulations,
1. Insert a char {a-z to A-Z} to a sequence
2. Delete a char in a sequence
3. Modify a char in a sequence
How many minimum manipulations are needed
to let both sequence are entirely different
A[i]!=B[i] i from 1 to min(len(A), len(B))
At first glance,
It seems that this could be solve be sequence alignment algorithm using dp
However the optimal substructure likely won't hold if you do it from the beginning
What are your thoughts?