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}