Let str1 and str2 be two strings of length m and n respectively. Our aim is to convert str1 to str2 in minimum number of operations.

Operations allowed are -

i) Insert

ii) Delete

iii) Replace

Let C[m][n] is the edit distance of converting str1 of length m to str2 of length n.

C[i][j] = edit distance of converting str1[1...i] into str2[1...j].

Then, following is the recurrence relation for this problem-

C[m][n] = C[m-1][n-1], if str1[m] = str2[n] i.e., we don't have to apply any operation since str1[m] = str2[n]

Now, if str1[m] != str2[n],

then, either we can replace str1[m] by str2[n] in which case the edit distance = 1 + C[m-1][n-1]

or we can insert str2[n] in front of str1[m-1] in which case the edit distance = 1 + C[m][n-1]

or we can delete str1[m] and the edit distance of converting str1 to str2 becomes 1 + C[m-1][n].

So, C[m][n] = minimum of the three i.e.,

C[m][n] = 1 + min(C[m-1][n-1], C[m-1][n], C[m][n-1]).

The time complexity of this algorithm is O(m*n)
and the space complexity is also the same i.e., O(m*n) .

But we can observe from above recurrence relation that to fill any entry C[i][j] we require only the two rows, i th row and (i-1)th row.

So the space complexity can be reduced to O(n).

The space complexity of my implementation is O(n).

```
#include <iostream>
#include <string>
using namespace std;
unsigned long long minOf(unsigned long long a, unsigned long long b, unsigned long long c) {
if(a < b && a < c)
return a;
if(b < c)
return b;
else
return c;
}
int main() {
string str1, str2;
cout<<"Enter string 1 : ";
cin>>str1;
cout<<"Enter string 2 : ";
cin>>str2;
unsigned long int m = str1.length();
unsigned long int n = str2.length();
unsigned long long *first, *second, *temp;
first = new unsigned long long[n+1];
second = new unsigned long long[n+1];
for(int i=0;i<=n;i++) {
first[i] = i; // as the str1 is empty so edit distance = number of characters in str2
}
for(int i=1;i<=m;i++) {
second[0] = i;
for(int j=1;j<=n;j++) {
if(str1[i-1] == str2[j-1]) {
second[j] = first[j-1]; // case 1
}
else {
second[j] = 1 + minOf(first[j-1], first[j], second[j-1]); // case 2
}
}
//swapping the pointers
temp = first;
first = second;
second = temp;
}
cout<<first[n]<<endl;
return 0;
}
```