# HackerRank Substring Diff problem solution

In this HackerRank Substring Diff problem solution, we have given two strings and an integer k and we need to determine the length of the longest common substrings of the two strings that differ in no more than the k positions.

## Problem solution in Python.

```#!/bin/python3

import os
import sys
from collections import deque

# Complete the substringDiff function below.
def substringDiff(k, s1, s2):
longest = 0
for d in range(-len(s1) + 1, len(s2)):
i = max(-d, 0) + d
j = max(-d, 0)
q = deque(maxlen=k)
s = 0
for p in range(0, min(len(s2) - i, len(s1) - j)):
if s1[i + p] != s2[j + p]:
if k > 0:
if len(q) == k:
s = q[-1] + 1
q.appendleft(p)
else:
s = p + 1
if p + 1 - s > longest:
longest = p + 1 - s
return longest

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

t = int(input())

for t_itr in range(t):
kS1S2 = input().split()

k = int(kS1S2[0])

s1 = kS1S2[1]

s2 = kS1S2[2]

result = substringDiff(k, s1, s2)

fptr.write(str(result) + '\n')

fptr.close()
```

{"mode":"full","isActive":false}

## Problem solution in Java.

```import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int T = s.nextInt();
for (int t = 0; t < T; t++) {
int S = s.nextInt();
String p = s.next();
String q = s.next();
int maxLen = 0;
for (int i = 0; i < p.length(); i++) {
for (int j = 0; j < q.length(); j++) {
if (p.charAt(i) != q.charAt(j)) continue;
int mismatches = 0;
int len = 0;
for (int k = 0; i + k < p.length() && j + k < q.length(); k++) {
if (p.charAt(i + k) != q.charAt(j + k)) mismatches++;
if (mismatches > S) break;
len++;
}
if (mismatches < S) {
for (int k = 1; i - k >= 0 && j - k >= 0; k++) {
if (p.charAt(i - k) != q.charAt(j - k)) mismatches++;
if (mismatches > S) break;
len++;
}
}
maxLen = Math.max(maxLen, len);
}
}
System.out.println(maxLen);
}
}
}
```

{"mode":"full","isActive":false}

## Problem solution in C++.

```/* Enter your code here. Read input from STDIN. Print output to STDOUT */

#include <iostream>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;

int gao(string &s, string &t, int k) {
int ret = 0, n = s.length();
for (int i = 0; i < n; ++i) {
queue<int> q;
int diff = 0;
for (int j = i; j < n; ++j) {
if (s[j] != t[j - i]) {
diff++;
}
q.push(j);
while (diff > k) {
int x = q.front();
q.pop();
if (s[x] != t[x - i]) {
diff--;
}
}
ret = max(ret, (int)q.size());
}
}
return ret;
}

int main() {
int T, k;
string s, t;
cin >> T;
while (T--) {
cin >> k >> s >> t;
cout << max(gao(s, t, k), gao(t, s, k)) << endl;
}
return 0;
}```

{"mode":"full","isActive":false}

## Problem solution in C.

```#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define MAX_SIZE 1500
int main(void){
int num_cases;
int k;
char string1[MAX_SIZE+1],string2[MAX_SIZE+1];
char diff_array[MAX_SIZE][MAX_SIZE];
int length;
int i;

scanf("%d",&num_cases);
while(num_cases--){
scanf("%d %s %s",&k,string1,string2);
length=strlen(string1);

int j;
for(i=0;i<length;i++){
for(j=0;j<length;j++)
diff_array[i][j]=(string1[i]!=string2[j]);
}
int front_pointer,back_ptr1,back_ptr2,front_sum1,front_sum2,curr_max=-1;
int back_sum1,back_sum2;
for(i=0;i<length;i++){
front_sum1=front_sum2=back_sum1=back_sum2=0;
back_ptr1=back_ptr2=-1;
for(front_pointer=0;front_pointer+i<length;front_pointer++){
front_sum1+=diff_array[front_pointer][i+front_pointer];
front_sum2+=diff_array[i+front_pointer][front_pointer];
while(front_sum1-back_sum1>k){
back_ptr1++;
back_sum1+=diff_array[back_ptr1][i+back_ptr1];
}
while(front_sum2-back_sum2>k){
back_ptr2++;
back_sum2+=diff_array[i+back_ptr2][back_ptr2];
}

if(front_pointer-back_ptr1>curr_max)
curr_max=front_pointer-back_ptr1;
if(front_pointer-back_ptr2>curr_max)
curr_max=front_pointer-back_ptr2;
}
}
printf("%d\n",curr_max);
}
return 0;
}```

{"mode":"full","isActive":false}