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.

Function Description

Complete the substringDiff function in the editor below. It should return an integer that represents the length of the longest common substring as defined.

substringDiff has the following parameter(s):

• k: an integer that represents the maximum number of differing characters in a matching pair
• s1: the first string
• s2: the second string

HackerRank Substring Diff 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()

Substring Diff 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);
        }
    }
}

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;
}

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("%dn",curr_max);
    }
    return 0;
}