Dynamic programming table for finding similar substrings is too large

Question

Substring Diff
Given two strings of length $n$, $P = p_1\dots p_n$ and $Q = q_1 \dots q_n$, we define $M(i, j, L)$ as the number of mismatches between $p_i \dots p_{i+L-1}$ and $q_j \dots q_{j+L-1}$. In set notation, $M(i, j, L)$ refers to the size of the set $\{0 \leq x < L \mid p_{i + x} \neq q_{j + x}\}$.

Given an integer $K$, your task is to find the maximum length $L$ such that there exists pair of indices $(i,j)$ for which we have $M(i, j, L) \leq K$. Of course, we should also have $i + L - 1 \leq n$ and $j + L - 1 \leq n$.

Constraints

• $0 \leq K \leq |P|$
• Both $P$ & $Q$ would have the same length
• The size of each of the string would be at the max 1500
• All characters in $P$ and $Q$ are lower-case English letters.

The recursive function will have the form:

longest(string1, string2, allowed_mismatches) = 
    {
        ... (something :P )
    }

The state space then has size $K^3$. With an upper bound on $K$ of 1500, the running time and space usage will be terrible... So direct dynamic programming will not work without some additional property to reduce the state space.

Ideas?

UPDATE

Using the ideas suggested by both Yuval and Vor, I came up with the following solution that works like a charm, running in $O(K^2)$ time and using $K$ space.

def longest_range_min_sum(str1, str2, start1, start2, slice_size, max_sum):
    longest = 0
    i = 0
    running_sum = 0
    while i + longest < slice_size:
        if str1[start1 + i + longest] != str2[start2 + i + longest]:
            running_sum += 1
        if running_sum > max_sum:
            if str1[start1 + i] != str2[start2 + i]:
                running_sum -= 1
            i += 1
        else:
            longest += 1
    return longest

import sys

data = sys.stdin.readlines()
num_cases = int(data.pop(0))
for ignore in xrange(num_cases):
    max_mismatches, str1, str2 = data.pop(0).split()
    max_mismatches = int(max_mismatches)
    m = n = len(str1)
    longest = 0
    for i in xrange(m + n + 1):
        if i > n:
            slice_size = m - (i - n)
        else:
            slice_size = min(i, m)
        if slice_size == 0:
            continue
        end1 = max(m, m - i)
        if i > n:
            end1 = m - (i - n)
        start1 = end1 - slice_size
        end2 = min(i, n)
        start2 = end2 - slice_size
        #print zeros_and_ones 
        #print str1[start1:end1], ' - ', str2[start2:end2]
        longest_in_sub = longest_range_min_sum(str1, str2, start1, start2, slice_size, max_mismatches)
        #print longest_in_sub
        longest = max(longest, longest_in_sub)
    print longest

Answer 1

One can reduce your problem to the following. Given a sequence of $N$ numbers, find a contiguous subsequence of length at most $K+1$ having maximal sum. This problem, in turn, is solvable in time $O(N)$.

What's the connection between your problem and mine? Let the positions of the mistakes be $I_1,\ldots,I_t$, and add $I_0 = 0$, $I_{t+1} = N+1$. The sequence in question is $J_1 = I_1 - I_0,\ldots,J_{t+1}=I_{t+1}-I_t$. Every $K+1$ consecutive numbers $J_a,\ldots,J_{a+K}$ correspond to a maximal solution for your problem of length $J_a + \cdots + J_{a+K} - 1$. The entire algorithm takes linear time.

Edit: This calculates the maximal $L$ such that $M(i,i,L) \leq K$ for some $i$. The actual problem wanted to find the maximal $L$ such that $M(i,j,L) \leq K$ for some $i,j$. By considering all possible shifts, we can solve this in $O(N^2)$ time and $O(K)$ space.

Answer 2

Using Yuval's reduction, the problem can be reformulated as "Find the largest range $(i,j)$ in a binary string $S \in \{0,1\}^*$ such that the number of $1$s contained in the range is $\leq K$" (see this question).

The idea is to start with an initial valid range $(0,j)$ of length $maxlen$ and then shift the "window" $(i,i+maxlen)$ to the right, checking at every step if maxlen can be increased.

This is the pseudocode of a possible solution:

 INPUT : string P and Q of length n, integer K
         // string indexes are 0 based (P[0] = first char of P)
 maxidx = 0   // position of the largest interval
 maxlen = 0   // length of the largest interval
 i = 0        // current position of the "window" (i,i+maxlen)
 diffsum = 0  // sum of the mismatches in the range (i,i+maxlen)
 while ( i + maxlen < n ) do
   // update the number of mismatches of the window:
   if (P[i + maxlen] != Q[i + maxlen]) then diffsum = diffsum + 1 
   if diffsum <= K
     then begin
       maxlen = maxlen + 1 // expand window
       maxidx = i  // update base pointer
     end
     else begin
       if (P[i] != Q[i]) then diffsum = diffsum - 1 // discard mismatches out of the window
       i = i + 1 // shift window to the right
     end

 OUTPUT : if maxlen > 0 
            then output (maxidx, maxidx + maxlen - 1) // output the largest interval
            else output("no range with # of mismatches <= K")

Time complexity: $O(n)$, space $O(1)$.