3 ms·
I’m not sure it is quadratic, but the “deleting the left or right character” to me, hint it deviates from linear. I think the solution, logically, is to cut th
by Someone 6y ago
I’m not sure it is quadratic, but the “deleting the left or right character” to me, hint it deviates from linear.
I think the solution, logically, is to cut the string in two halves, duplicating the center character for odd-length strings (¿or can you ignore it a bit more?), computing edit distance between the front half and the reversed right half, allowing only deletions, and bailing out as soon as you know the answer is larger than one.
In real life, optimize away the “cut into two halves” and “reverse” parts, as they will be expensive.