Substring Diff | HackerRank (Algorithms) | Longest Common Substring

Problem

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 , determine the length of the longest common substrings of the two strings that differ in no more than k positions.

Hackerrank Problem Link

Input

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, s1 and s2.

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

Output

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

Constraints

  • 1 <= T <= 10
  • 1 <= k <= | s1 |
  • | s1 | = | s2 |
  • 1 <= | s1 | , | s2 | <= 1500

Sample Input

3
2 tabriz torino
0 abacba abcaba
3 helloworld yellomarin

Sample Output

4
3
8

Explanation
Test Case #01: 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.

Solution

//
//  main.cpp
//  Substring Diff
//
//  Created by Himanshu on 21/02/22.
//
 
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
using namespace std;
 
int main() {
    int T;
    cin>>T;
     
    while (T--) {
        long ans = 0, k;
        string p, q;
        
        cin>>k>>p>>q;
         
        int n = (int) p.size();
        long *currk = new long [2*n+1]();
        auto st = new long [2*n+1][2]();
        long lcs[n+1][n+1];
        memset(lcs, 0, sizeof(lcs[0][0]) * (n+1) * (n+1));
         
        for (int i=0; i<=n; i++) {
            for (int j=0; j<=n; j++) {
                currk[i-j+n] = 0;
                if (i >= j) {
                    st[i-j+n][0] = i-j+1;
                    st[i-j+n][1] = 1;
                } else {
                     st[i-j+n][0] = 1;
                     st[i-j+n][1] = j-i+1;
                }
            }
        }
         
        for(int i=0; i<=n; i++) {
            for(int j=0; j<=n; j++) {
                
                //Longest Common Substring DP
                if (i == 0 || j == 0) {
                    lcs[i][j] = 0;
                    currk[i-j+n] = 0;
                } else if (p[i-1] == q[j-1]) {
                    lcs[i][j] = lcs[i-1][j-1] + 1;
                } else if (p[i-1] != q[j-1]) {
                    lcs[i][j] = lcs[i-1][j-1] + 1;
                    currk[i-j+n]++;
                }
                 
                //Sliding Window technique
                if (currk[i-j+n] > k) {
                    long l, m, ctr = 0, flag = 0;
                     
                    for(l=st[i-j+n][0], m=st[i-j+n][1]; l<i && m<j; l++, m++) {
                        ctr++;
                        if (p[l-1] != q[m-1]) {
                            flag = 1;
                            break;
                        }
                    }
                     
                    if (flag) {
                        lcs[i][j] = lcs[i-1][j-1] - ctr + 1;
                        st[i-j+n][0] = l+1;
                        st[i-j+n][1] = m+1;
                        currk[i-j+n]--;
                    }
                }
                 
                if (lcs[i][j] > ans) {
                    ans = lcs[i][j];
                }
            }
        }
         
        printf("%ld\n",ans);
    }
    
    return 0;
}

Time Complexity: O(n^2)

Leave a Reply

Your email address will not be published.