HackerRank Substring Diff Problem Solution

In this post, we will solve HackerRank Substring Diff Problem Solution.

In this problem, we’ll use the term “longest common substring” loosely. It refers to substrings differing at some number or fewer characters when compared index by index.
For example, ‘abc’ and ‘adc’ differ in one position, ‘aab’ and ‘aba’ differ in two.
Given two strings and an integer k. determine the length of the longest common substrings of the two strings that differ in no more than k positions.
For example, k = 1. Strings $1 = abcd and s2 = bbca. Check to see if the whole string (the longest substrings) matches. Given that neither the first nor last characters match and 2 > k. we need to try shorter substrings. The next longest substrings are 81′ = [abc, bcd] and $2′ = [bbc, bca]. Two pairs of these substrings only differ in 1 position: [abc, bbc] and [bed, bea]. They are of length 3.

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

Input Format
The first line of input contains a single integer, t, the number of test cases follow.
Each of the next t lines contains three space-separated values: an integer k and two strings,
$1 and $2.

Output Format
For each test case, output a single integer which is the length of the maximum length common substrings differing at k or fewer positions.

Sample Input

3
2 tabriz torino
0 abacba abcaba
3 helloworld yellomarin

Sample Output

4
3
8

Explanation

First test case: If we take “briz” from the first string, and “orin” from the second string. then the number of mismatches between these two substrings is equal to 2 and their lengths are 4.
Second test case: Since k = 0, we should find the longest common substring, standard definition, for the given input strings. We choose “aba” as the result.
Third test case: We can choose “hellowor” from first string and “yellomar” from the second string

HackerRank Substring Diff Problem Solution

Substring Diff C Solution

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

int L (int t0, int k, char* p, char* q, int n) 
{
	int s, t, i, j, z, m, last, l, mi, mj;

	int coords = 0;
	int* x = (int*) malloc(sizeof(int)*n*n);
	int* y = (int*) malloc(sizeof(int)*n*n);
	for (i = 0; i < n*n; i++) {
		x[i] = -1;
		y[i] = -1;		
	}

	int** score = (int**) malloc(sizeof(int*)*n);
	for (i = 0; i < n; i++) {
		score[i] = (int*) malloc(sizeof(int)*n);
		for (j = 0; j < n; j++) {
			if (q[i] != p[j]) {
				score[i][j] = 1;
			} else {
				score[i][j] = 0;
				x[coords] = i;
				y[coords++] = j;
			}
		}
	}

	if (coords == 0) { // score has only 1s
		return (k > n ? n : k);
	}

	l = 0;
	for (s = 0; s < coords; s++) {
		i = x[s];
		j = y[s];
		m = 0;
		last = -1;
		z = n - (i > j ? i : j);
		for (t = 0; t < n; t++) {
			//printf("** (%d %d %d) (%d %d)\n", i, j, t+1, i-(t-z+1), j-(t-z+1));
			if (t >= z) {
				int mi, mj;
				mi = i-(t-z+1);
				mj = j-(t-z+1);	
				if (mi < 0 || mj < 0)
					break;	
				m += score[mi][mj];
				//if (t+1 == 601)				
				//printf("* %d %d %d = %d <= %d [%d]\n", mi, mj, t+1, m, k, n);
			} else {
				m += score[i+t][j+t];
				//if (t+1 == 601)		
				//printf("%d %d %d = %d <= %d [%d]\n", i, j, t+1, m, k, n);
			}
			if (m <= k) {
				last = t+1;
				if (last == n) {
					free(score);
					free(x);
					free(y);
					return last;
				}
			} else {
				break;
			}
		}
		if (last != -1 && last > l)
				l = last; 
	}
	free(score);
	free(x);
	free(y);
	return l;
}

int main() 
{
    int t, k, n, result, r;
    char p[1501];
    char q[1501];
    r = scanf("%d%*c", &t);
	int x = 3;
    for (; t > 0; t--) {
		x--;
        r = scanf("%d %s %s%*c", &k, p, q);
        for (n = 0; p[n] != '\0'; n++);
		result = L(n, k, p, q, n);
        printf("%d\n", result);
    } 
    return 0;
}

Substring Diff C++ Solution

#include <iostream>
using namespace std;

int M(string& P, string& Q, int i, int j, int S) {
    auto result = 0, L = 0;
    for(auto k = 0; i + L < P.size() && j + L < Q.size(); ) {
        if(P[i + L] != Q[j + L]) {
            k++;
        }
        if(k > S) {
            result = max(result, L);
            while(P[i] == Q[j]) {
                i++;
                j++;
                L--;
            }
            i++;
            j++;
            k--;
        } else {
            L++;
        }
    }
    return max(result, L);
}

int main() {
    int T, S;
    cin >> T;
    for(string P, Q; cin >> S >> P >> Q; ) {
        auto result = M(P, Q, 0, 0, S);
        for(auto i = 1; i < P.size(); i++) {
            auto m = max(M(P, Q, 0, i, S), M(P, Q, i, 0, S));
            if(m > result) {
                result = m;
            }
        }
        cout << result << endl;
    }
    return 0;
}

Substring Diff C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
class Solution {
    static void Main(String[] args) {
        int tc = int.Parse(Console.ReadLine());
        while (tc-- > 0) {
            var tmp = Console.ReadLine().Split(' ');
            int s = int.Parse(tmp[0]);
            string first = tmp[1];
            string second = tmp[2];
            int n = first.Length;

            if (s == n) { Console.WriteLine(n); continue; }
            var hash = new HashSet<int>();
            int L = 0;

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (hash.Contains(j - i)) continue;
                    hash.Add(j - i);

                    int diff = 0, len = n - Math.Max(i, j);
                    if (len > L) {
                        int[] w = new int[len];

                        for (int k = 0; k < len; k++) {
                            if (first[i + k] != second[j + k]) {
                                diff++;
                            }
                            w[k] = diff;
                        }

                        for (int k = len - 1; k + 1 > L; k--) {
                            if (w[k] <= s) { L = k + 1; }
                        }
                        for (int k = len - 1; k > L; k--) {
                            int low = 0, high = len - 1;
                            int d = w[k] - s;
                            while (high - low > 1) {
                                int mid = (high + low) / 2;
                                if (w[mid] >= d) high = mid; else low = mid;

                            }
                            if (w[k] - w[high] <= s) { L = Math.Max(L, k - high); }
                        }
                    }
                }
            }

            Console.WriteLine(L);
        }
    }
}

Substring Diff Java Solution

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

Substring Diff JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.replace(/\s*$/, '')
        .split('\n')
        .map(str => str.replace(/\s*$/, ''));

    main();
});

function readLine() {
    return inputString[currentLine++];
}

// Complete the substringDiff function below.
function substringDiff(k, s1, s2) {
   const STR_LEN = s1.length;  //  s1, s2 has the same length

    let s1s2Dif = [];
    for (let i = 0; i < STR_LEN; i++)
        s1s2Dif.push([]);

    // step 1, initialize difference array
    for (let i = 0; i < STR_LEN; i++) {
        let row = s1s2Dif[i];
        for (let j = 0; j < STR_LEN; j++)
            row[j] = ((s1[i] !== s2[j]) ? 1 : 0);
    }

    // step 2, 
    let maxSubStr = 0;
    for (let gap = 0; gap < STR_LEN; gap++) {
        let frontPtr = 0, backPtr1 = -1, backPtr2 = -1;
        let frontSum1 = 0, backSum1 = 0, frontSum2 = 0, backSum2 = 0;

        for (; frontPtr + gap < STR_LEN; frontPtr++ ) {
            frontSum1 += s1s2Dif[frontPtr][frontPtr + gap];
            frontSum2 += s1s2Dif[frontPtr + gap][frontPtr];

            while (frontSum1 - backSum1 > k) {
                backPtr1++;
                backSum1 += s1s2Dif[backPtr1][backPtr1 + gap];
            }

            while (frontSum2 - backSum2 > k) {
                backPtr2++;
                backSum2 += s1s2Dif[backPtr2 + gap][backPtr2];
            }

            maxSubStr = Math.max(maxSubStr, frontPtr - backPtr1);
            maxSubStr = Math.max(maxSubStr, frontPtr - backPtr2);
        }
    }

    return maxSubStr;
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const t = parseInt(readLine(), 10);

    for (let tItr = 0; tItr < t; tItr++) {
        const kS1S2 = readLine().split(' ');

        const k = parseInt(kS1S2[0], 10);

        const s1 = kS1S2[1];

        const s2 = kS1S2[2];

        let result = substringDiff(k, s1, s2);

        ws.write(result + "\n");
    }

    ws.end();
}

Substring Diff Python Solution

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'substringDiff' function below.
#
# The function is expected to return an INTEGER.
# The function accepts following parameters:
#  1. INTEGER k
#  2. STRING s1
#  3. STRING s2
#

def l_func(p,q,max_s):
    n = len(q)
    res_ar = [0]
    count = 0
    ans = 0
    for i in range(n):
        if(p[i]!=q[i]):
            res_ar.append(i+1)
            count += 1
            if(count>max_s):
                l = res_ar[-1]-res_ar[-2-max_s]-1
                if(l>ans):ans = l
    if(count<=max_s):
        return n
    return ans

def check_func(p,q,s):
    n = len(q)
    ans = 0
    for i in range(n):
        if(n-i<=ans):break
        l = l_func(p,q[i:],s)
        if(l>ans):
            ans = l
    for i in range(n):
        if(n-i<=ans):break
        l = l_func(q,p[i:],s)
        if(l>ans):
            ans = l
    return ans
for case_t in range(int(input())):
    str_s,p,q = input().strip().split()
    s = int(str_s)
    print(check_func(p,q,s))

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python