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.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Substring Diff
  5. Discussions

Substring Diff

Sort by

recency

|

75 Discussions

|

  • wifivop476
     + 0 comments

    You could definately just write a function to do both forloops cus the for loops are basically identical but ceebs. IF your wondering why theres two, i liook at all the diagonals sprouting from each edge of the index (top and left seperately) cus im not good enuff to do it in one loop. underwired sports bras

  • charlesjordan001
     + 0 comments

    Very Beneficial for programers.

  • dehaka
     + 0 comments

    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

    void dehaka(vector<vector<int>>& M, queue<int>& Q, int k, int i, int j) {
    if (Q.size() < k) {
        M[i][j] = M[i-1][j-1] + 1;
        Q.push(max(i, j));
    }
    else if (Q.size() == k) {
        M[i][j] = max(i, j) - Q.front();
        Q.pop();
        Q.push(max(i, j));
    }
}

int substringDiff(int k, string s1, string s2) {
    int answer = 0;
    vector<vector<int>> M(s1.size()+1, vector<int>(s2.size()+1, 0));
    vector<queue<int>> QS1(s1.size()), QS2(s2.size());
    for (int i=1; i <= s1.size(); i++) {
        for (int j=1; j <= s2.size(); j++) {
            if (s1[i-1] == s2[j-1]) M[i][j] = M[i-1][j-1] + 1;
            else if (i >= j and k > 0) {
                dehaka(M, QS1[i-j], k, i, j);
            }
            else if (i < j and k > 0) {
                dehaka(M, QS2[j-i], k, i, j);
            }
            answer = max(answer, M[i][j]);
        }
    }
    return answer;
}

  • ajm03m
     + 1 comment

    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.

    def substringDiff(k, s1, s2):
    # Write your code here
    
    def matches(str1, str2):
        maxLen = 0
        lengthS1 = len(str1)
        lengthS2 = len(str1)
        for idx in range(lengthS1):
            j = 0
            queue = deque()
            res = [0] * 2
            trackLen = 0
            for i in range(idx, lengthS1):
                if j > lengthS2: # ensure doesnt exceed
                    break
                    
                if str1[i] == str2[j]:
                    res[1] += 1
                    queue.append(1)
                    trackLen += 1
                else: 
                    res[0] += 1
                    queue.append(0)
                    trackLen += 1
                while res[0] > k:
                    val = queue.popleft()
                    res[val] -= 1
                    trackLen -= 1
                if trackLen > maxLen:
                    maxLen = trackLen
                j += 1
        return maxLen

    return max(matches(s1, s2), matches(s2, s1))
# n 0 0 0 0 0 0
# o 0 0 0 0 0 0

  • bluephirus
     + 0 comments

    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.

      a b a c b a 
a 0 1 0 1 1 0
b 1 0 1 1 0 1
c 1 1 1 0 1 1
a 0 1 0 1 1 0
b 1 0 1 1 0 1
a 0 1 0 1 1 0

    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

    [0]=0
[1]=11
[2]=101
[3]=0110
[4]=11011
[5]=001100
[6]=1111
[7]=000
[8]=11
[9]=0

    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.

            loop through the diffArray.
        while current_slice_sum + next_slice < maxTargetDiff 
				    move_start_slice
            recalculate_slice_length

        current_slice_sum = current_slice_sum + next_slice
        recalculate_slice_length

        if maxLength < currentLength:
            maxLength = currentLength

    return maxLength