We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Substring Diff
Substring Diff
Sort by
recency
|
73 Discussions
|
Please Login in order to post a comment
a modified version of the method for longest common substring, O(nm), each step in the matrix M takes constant time
for each i,j, this finds the longest consecutive common substring of s1, s2, ending at s1[i] and s2[j], then it takes the max of all these length
Didnt see a good python solution for this problem. Mine is O(n * m) solution (n,m are lens of s1 and s2).
It basically looks at diagonals how @bluephirus described it.
After reading @kiwi71728 comments, it explain great. My approach is different, but I don't have any strong theory, but the logic is the same with what kiwi71728 explain.
What I do is first create matrix difference.
From the matrix difference in there, I realized the the diagonal \ is the k we search. Then I add it to the list. From the matrix in there, the list become
Then loop again from the list to slice for each item in the list, the find the longest length if the sum is the same or less with k.
One approach to solve the Longest Common Substring (LCS) problem involves aligning the two strings and iterating over possible alignments to find the longest match. Given two strings, e.g., "abcde" and "efghicd" with LCS "cd", the alignment could look like:
Multiple such alignments are possible. By iterating over these alignments and comparing characters, we can discover the LCS.
Below is the implementation of this method to find LCS:
In the algorithm, we use variables
aStart
,aEnd
, andbStart
to manage slices of the stringsa
andb
for each alignment. Thetmp
string accumulates matching characters until we encounter a mismatch or reach the end. Iftmp
's length surpasses the currentresult
, we update theresult
.Given two strings, the challenge is to find the length of the longest common substring that has no more than 'k' differing characters. We approach this problem by adapting our earlier longest common substring algorithm, specifically by replacing Section A with Section B to account for the differences allowed.
Here's how our adapted algorithm works:
To understand the algorithm:
diffIndices
).diffIndices
to find the longest substring that has exactlyk
differences.To determine the time complexity of the algorithm, we need to focus on the number of iterations our inner loop performs.
Given two strings
a
andb
with lengthsn = |a|
andm = |b|
respectively, and assumingn <= m
, the number of iterations in the inner loop can be captured as:n
integers for the increasing overlap ofa
withb
:1 + 2 + ... + n
which equalsn(n+1)/2
.n(m-n)
iterations for the middle section wherea
slides overb
with a constant length ofn
.n-1
to1
for the decreasing overlap ofa
as it exitsb
:n-1 + n-2 + ... + 1
which equalsn(n-1)/2
.Combining these:
n(n+1)/2 + n(m-n) + n(n-1)/2
=n^2 + nm - n^2
=nm
Therefore, the time complexity of the algorithm is O(nm).
Here is my solution in java, javascript, python, C, C++, Csharp HackerRank Substring Diff Problem Solution