Check whether Strings are K Distance Apart or Not

Difficulty Level Medium
Frequently asked in Amazon Deutsche Bank Facebook GE Healthcare Microsoft
Dynamic Programming Matrix String

Problem Statement

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

Input Format

The first line will contain an integer value K. And the second and third line contains s1(first string) and s2(second string).

Output Format

Print “TRUE” if these string are k distance apart otherwise print “FALSE“.

Constraints

  • 1<= |S1|, |S2|<=10^3
  • String only contains small case alphabets.

Example

2
cat
cade
TRUE

Algorithm for Check whether Strings are K Distance Apart or Not

  • Take input by following the above format.
  • Find the distance for both the string and check the difference between them. If the difference is greater than k print “FALSE“.
  • Create a dp matrix of (n+1)*(m+1) size and fill it in a bottom-up manner.

1. If the length of s1 is zero then insert all characters of the second-string.

2. If the length of s2 is zero then remove all characters of second-string.

3. If the last characters are the same, ignore the last char and recur for the remaining string.

See also
OSI Model

4. If the last character is different, consider all possibilities, and find the minimum.

  • If the value of dp[n][m] is less than or equal to k then print “TRUE” otherwise “FALSE“.

Implementation

C++ Program for Check whether Strings are K Distance Apart or Not

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int k;
    cin>>k;
    string s1,s2;
    cin>>s1>>s2;
    int n=s1.length();
    int m=s2.length();
    if(abs(n-m)>k)
    {
        cout<<"FALSE"<<endl;
    }
    else
    {
        int dp[n+1][m+1];
        for(int i=0;i<=m;i++)
        {
            dp[0][i]=i;
        }
        for(int i=0;i<=n;i++)
        {
            dp[i][0]=i;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(s1[i-1]==s2[j-1])
                {
                    dp[i][j]=dp[i-1][j-1];
                }
                else
                {
                    dp[i][j]= 1 + min(dp[i][j - 1], min(dp[i - 1][j], dp[i - 1][j - 1]));
                }
            }
        }
        if(dp[n][m]<=k)
        {
            cout<<"TRUE"<<endl;
        }
        else
        {
            cout<<"FALSE"<<endl;
        }
    }
}

Java Program for Check whether Strings are K Distance Apart or Not

import java.util.Scanner;

class sum { 
    public static void main(String[] args) 
    {
        Scanner sr= new Scanner(System.in);
        int k = sr.nextInt();
        String s1= sr.next();
        String s2= sr.next();
        int n = s1.length(); 
        int m = s2.length();
        if(Math.abs(m-n)>k)
        {
            System.out.println("FALSE");
        }
        else
        {
            int dp[][] = new int[n+1][m+1];
            for(int i=0;i<=m;i++)
            {
                dp[0][i]=i;
            }
            for(int i=0;i<=n;i++)
            {
                dp[i][0]=i;
            }
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=m;j++)
                {
                    if(s1.charAt(i-1)==s2.charAt(j-1))
                    {
                        dp[i][j]=dp[i-1][j-1];
                    }
                    else
                    {
                        dp[i][j]= 1 + Math.min(dp[i][j - 1], Math.min(dp[i - 1][j], dp[i - 1][j - 1]));
                    }
                }
            }
            if(dp[n][m]<=k)
            {
                System.out.println("TRUE");
            }
            else
            {
                System.out.println("FALSE");
            }
            }
    } 
}
4
TutorialCup
TutorCup
TRUE

Complexity Analysis for Check whether Strings are K Distance Apart or Not

Time Complexity

O(n*m) where n is the size of the first string and m is the size of the second string. Here we fill dp of size (n+1)*(m+1) in bottom-up manner.

Space Complexity

O(n*m) where n is the size of the first string and m is the size of the second string. We use the dp matrix for finding the result here.

Reference