making two strings into one

Question

Let's say I have 2 strings

AAABBBCCCCC

and

AAAABBBBCCCC

to make these strings as similar as possible, given that I can only remove characters I should

• delete the last C from the first string
• delete the last A and the last B from the second string,

so that they become

AAABBBCCCC

What would be an efficient algorithm to find out which characters to remove from each string?

I'm currently crushing my brain cells thinking about a sollution involving substrings of the strings, looking for them i,n the other string.

Answer 1

Levenshtein distance can calculate how many changes you need to convert one string into another. A small change to the source, and you may get not only distance, but the conversions needed.