Check whether Strings are K Distance Apart or Not

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.

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