making two strings into one
algorithm, python, string
Solution
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.
Problem
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.