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

  • 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