Given binary number $n~$, count the number of every possible couple of suffix and prefix such that their edit distance will be in the given interval . I know solution for $O(n^4)$ (classical edit distance algorithm with memoization). But I was told that there exist solution in $O(n^3)$.
My idea is to use cycle - for every prefix $p$ in $n$ for every suffix $s$ in $n$ - and remember the solution of the previous suffix. We could say with certainty that the editorial distance of the current suffix and prefix is $\le$ editDist of previous suffix and the same prefix $+ 1$ (simply delete the first element of suffix) but since there is required minimal distance we can not use this tweak, even tough there would be no minimal distance we can not say that that this little tweak will reduce the time complexity to $O(n^3)$.
Can someone give me a hint or solution how to solve this problem in $O(n^3) ~?$