Home » Technical Interview Questions » String Interview Questions » Check whether strings are k distance apart or not

# Check whether strings are k distance apart or not

INPUT
s1 = “cat”
k = 2

OUTPUT
TRUE

## Algorithm

1. If the difference between length of the given strings is greater than k or not. If it is greater then return FALSE

2. Find the edit distance of two strings, if edit distance is less than or equal to k then return TRUE
Here edit distance  is the number of edit operations(insert, remove, replace) to convert s1 to s2

## C++ Program

```#include<bits/stdc++.h>
using namespace std;

// finding minimum of three numbers
int min(int x, int y, int z)
{
return min(min(x, y), z);
}

int findEditDistance(string s1, string s2, int m, int n)
{
// table to store results of subproblems
int res[m+1][n+1];

// Fill res[][] in bottom up manner
for (int i=0; i<=m; i++)
{
for (int j = 0; j<=n; j++)
{
//If s1 string empty, then fill with s2
if (i == 0)
res[i][j] = j;

//If s2 string empty, then fill with s1
else if (j == 0)
res[i][j] = i; // Min. operations = i

// If last characters are same,recur for remaining string
else if (s1[i-1] == s2[j-1])
res[i][j] = res[i-1][j-1];

// If last character are different, consider all
else
res[i][j] = 1 + min(res[i][j-1],  // Insert
res[i-1][j],  // Remove
res[i-1][j-1]); // Replace
}
}

return res[m][n];
}

//if they are k distance apart returns true
bool areKDistant(string s1, string s2, int k)
{
int m = s1.length();
int n = s2.length();

if (abs(m-n) > k)
return false;

return (findEditDistance(s1, s2, m, n) <= k);
}

int main()
{
string s1 = "cat";