I recently encountered a problem in a contest.It was very similar to edit distance.Only difference was that we are also given cost of each of the operation insert,delete and replace .We have to find minimum cost to convert string1 to string2. This problem is fairly standard and can be solved using dynamic programming in O(n^2) time. The problem statement for Edit Distance can be found here: Problem

But the constraints given in the contest were n<=100000 so larger test cases won't pass in O(n^2). So is there any way to bring the time complexity of the solution?