Removing minimal letters from a string 'A' to remove all instances of string 'B'

algorithm, string

Solution

Solve it with dynamic programming. Let dp[i][j] the minimum operator to make A[0...i-1] have a suffix of B[0...j-1] as well as A[0...i] doesn't contain B, `dp[i][j] = Infinite` to index the operator is impossible. Then

if(A[i-1]=B[i-1]) 
   dp[i][j] = min(dp[i-1][j-1], dp[i-1][j])    
else dp[i][j]=dp[i-1][j]`,

return min(A[N][0],A[N][1],...,A[N][M-1]);`

Problem

If we have string `A` of length N and string `B` of length M, where M < N, can I quickly compute the minimum number of letters I have to remove from string `A` so that string `B` does not occur as a substring in `A`? If we have tiny string lengths, this problem is pretty easy to brute force: you just iterate a bitmask from `0` to `2^N` and see if `B` occurs as a substring in this subsequence of `A`. However, when N can go up to 10,000 and M can go up to 1,000, this algorithm obviously falls apart quickly. Is there a faster way to do this? Example: A=`ababaa` B=`aba`. Answer=`1`.Removing the second `a` in A will result in `abbaa`, which does not contain `B`. Edit: User n.m. posted a great counter example: `aabcc` and `abc`. We want to remove the single `b`, because removing any `a` or `c` will create another instance of the string `abc`.

Original source