Given a binary string s of length $n>2$.An edit operation is a single character insert, delete or substitution. The edit distance between two strings is the minimum number of edit operations needed to transform one string into the other one. How can I calculate the max edit distance between the given binary string and all the binary strings with the same length $n$.
It's not hard for me to think about a Brute Force method to solve the problem in $O(2^n*n^2)$,however the solution is quite disappointing. Any better ideas to solve the problem?
For some cases my BF solutions were:
- s="0111001010100" answer=9 from "0000111111111"
- s="001100101" answer=6 from "110000000"
- s="01110010101" answer=7 from "00001111000"
There might be one or more than one valid strings with the same answer.