Check whether strings are k distance apart or not

Given two strings and an integer k, write a function to check whether the given strings are k distance apart or not. That is if any charcater is mismatched or any character is to be removed then it is known as k disance apart


s1 = "cat"
s2 = "cade"
k = 2



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

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
                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";
    string s2 = "cade";
    int k = 2;
    areKDistant(s1, s2, k)? cout << "TRUE": 
                                cout << "FALSE";
    return 0;
Try It


< Prev
Scroll to Top