# Check whether Strings are K Distance Apart or Not

Difficulty Level Medium
Dynamic Programming Matrix StringViews 2429

## 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.

```2
cat
`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[i]=i;
}
for(int i=0;i<=n;i++)
{
dp[i]=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[i]=i;
}
for(int i=0;i<=n;i++)
{
dp[i]=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

Translate »