Substring Diff : Challenge | Dynamic Programming | Algorithms | HackerRank
Given two strings of lengthn , M(i,j,k) as the number of mismatches between p(i),p(i+1),...p(i+k−1) and q(j),q(j+1)...,q(j+k−1) . That is, in set notation, M(i,j,k) refers to the size of the set
S , your task is to find the maximum length L , such that there exists a pair of indices (i,j) for which we have M(i,j,L)≤S . Of course, we should also have i+L−1≤n and j+L−1≤n .
https://www.quora.com/What-is-the-algorithmic-approach-to-solve-hackerrank-problem-Substring-Diff
private int solveFast() {
int maxLen = 0;
for (int i = 0; i < n; i++) {
int m = solveFastSegment(i, 0);
maxLen = Math.max(maxLen, m);
}
for (int j = 0; j < n; j++) {
int m = solveFastSegment(0, j);
maxLen = Math.max(maxLen, m);
}
return maxLen;
}
private int solveFastSegment(int i, int j) {
int len = Math.min(n - i, n - j);
short[] d = new short[len];
for (int k = 0; k < len; k++) {
d[k] = (short) ((a[i + k] != b[j + k]) ? 1 : 0);
}
int l = 0;
int sumMismatch = 0;
int answer = 0;
for (int r = 0; r < len; r++) {
// let's add it to the sum anyway
sumMismatch += d[r];
// do we need to advance l now?
while (sumMismatch > maxMismatch) {
sumMismatch -= d[l++];
}
// update answer
answer = Math.max(answer, r - l + 1);
}
return answer;
}
Note that the O(N³) solution is pretty straightforward. For every (i,j) pair, find the largest value of L such that M(i,j,L) ≤ k. Since there are O(N²) such pairs and you need O(N) operations to calculate maximum L for each pair (You only need one operation to calculate M(i,j,L+1) when you have M(i,j,L) calculated already), the entire algorithm takes O(N³) time.
http://www.cnblogs.com/tonix/p/4486645.html
Read full article from Substring Diff : Challenge | Dynamic Programming | Algorithms | HackerRank
Given two strings of length
P = p1p2...pn and Q = q1q2...qn, we define {0 <= x < k, p[i+x]| ≠ q[j+x]} https://www.quora.com/What-is-the-algorithmic-approach-to-solve-hackerrank-problem-Substring-Diff
private int solveFast() {
int maxLen = 0;
for (int i = 0; i < n; i++) {
int m = solveFastSegment(i, 0);
maxLen = Math.max(maxLen, m);
}
for (int j = 0; j < n; j++) {
int m = solveFastSegment(0, j);
maxLen = Math.max(maxLen, m);
}
return maxLen;
}
private int solveFastSegment(int i, int j) {
int len = Math.min(n - i, n - j);
short[] d = new short[len];
for (int k = 0; k < len; k++) {
d[k] = (short) ((a[i + k] != b[j + k]) ? 1 : 0);
}
int l = 0;
int sumMismatch = 0;
int answer = 0;
for (int r = 0; r < len; r++) {
// let's add it to the sum anyway
sumMismatch += d[r];
// do we need to advance l now?
while (sumMismatch > maxMismatch) {
sumMismatch -= d[l++];
}
// update answer
answer = Math.max(answer, r - l + 1);
}
return answer;
}
Note that the O(N³) solution is pretty straightforward. For every (i,j) pair, find the largest value of L such that M(i,j,L) ≤ k. Since there are O(N²) such pairs and you need O(N) operations to calculate maximum L for each pair (You only need one operation to calculate M(i,j,L+1) when you have M(i,j,L) calculated already), the entire algorithm takes O(N³) time.
https://codepair.hackerrank.com/paper/iaItDyWm?b=eyJyb2xlIjoiY2FuZGlkYXRlIiwibmFtZSI6ImplZmZlcnl5dWFuIiwiZW1haWwiOiJ5dWFueXVuLmtlbm55QGdtYWlsLmNvbSJ9
private int solveNaive() {
int maxLen = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
int mismatch = 0;
for (int k = 0; i + k < n && j + k < n; k++) {
if (a[i + k] != b[j + k]) {
mismatch++;
}
if (mismatch <= maxMismatch) {
maxLen = Math.max(maxLen, k + 1);
}
}
}
return maxLen;
}
http://www.cnblogs.com/tonix/p/4486645.html
Read full article from Substring Diff : Challenge | Dynamic Programming | Algorithms | HackerRank
