# Longest subsequence without string

Does there exist a dynamic programming algorithm to find the longest subsequence in a string X that does not contain Y as substring? Just that this problem seems so similar to other DP string algorithms such as longest common subsequence and string. It must be able to handle occurrences of Y that overlap.

It seems that this might be a 2-state DP problem, with the state [s_pos, t_pos] being the longest subsequence of string S starting at s_pos that does not have sting T[t_pos..M] as a substring. N is the length of string S and M is the length of string T. However, my transitions are not correct: it does not get the case where S=`aaabc` and T=`aabc`. The problem is in the else statement - I don't know how to transition if the characters are equal. Actually I feel that the if branch is wrong... anyone know what could be wrong?

It even fails the case S=`aaab` and T=`aab`. I can explain why it fails: assuming I call solve(0, 0). solve(0, 0) calls solve(1, 1). solve(1, 1) calls solve(2, 2). Since s[2] != t[2], it restarts the search from solve(3, 0). However, aab is a substring and it never checks this or considers this case...

``````int solve(int s_pos, int t_pos)
{
if (s_pos >= N || t_pos >= M) return 0;
if (t_pos == M - 1 && s[s_pos] == t[t_pos]) return 0;
int ret = 0;
if (s[s_pos] != t[t_pos])
{
int tmp = solve(s_pos + 1, 0);
ret = max(ret, tmp + 1);
}
else
{
for (int i = s_pos + 1; i < N; i++)
{
int tmp = solve(i, t_pos + 1);
if (tmp != 0)
{
ret = max(ret, 1 + tmp);
}
}
}
return ret;
}
``````
• find all substrings Y in X and find the longest gap between them – ratchet freak Mar 10 '13 at 18:25
• what if they overlap? (the occurances) – user83834 Mar 10 '13 at 18:27
• Looks too much an homework for my taste to give a full solution. Here is an hint: if you knew for a given position the longest subsequence until that position and the longest subsequence ending at that position, could you update that for the next position? – AProgrammer Mar 10 '13 at 18:31
• @AProgrammer By next do you mean position i+1? – user83834 Mar 10 '13 at 18:34
• @ratchetfreak if X was OPPOPPO and Y was OPPO, there would be no gap. But the longest subsequence would be to ignore the middle O: OPPPPO. – user83834 Mar 10 '13 at 19:11

This should do the trick. I wrote it in a meta code similar to basic.

``````LONGEST = ""
while N>0
POS = find(T,S)
if POS>0 then
SUB = left(S,POS)
else
SUB = S
POS = N
endif
if len(SUB) > len(LONGEST) then
LONGEST = SUB
endif
N = N-POS
wend
``````

I think the main problem is your for loop inside the else statement, that then calls the function recursively.

Pick an approach, either recursion or iterate, but mixing them just seems wrong.

I would go with the iterative approach.

I would create an empty list outside the function.

Then call `solve`.

In this function try this approach:

Loop through the string: If the current character is not the start of the subsequence then put the character in a holding string. This will build up a string. If it starts the subsequence then add those characters to another holding string. Mark how many matches you have against the subsequence. One each character, if already matching against the subsequence, then look to see if it matches the first character, then if it matches the character at the next position to be matched. If it matches the subsequence then everything before that (in the holding string) is put into the list.

So, basically you need to track what may be a possible sequence that may win, and you need to track that a subsequence may be inside another subsequence.

You may need multiple holding strings, but implement a simple approach, with two holding strings, then go through various examples and write down what is happening in each step until you see if there is a need for another holding string.

I think you need to treat the Y substring like a regular expression and transform it into a DFA. Then you pass the input through the DFA, tracking how long its been since you've had a match. It seems like a linear-time problem, assuming the size of the input is much larger than the complexity of the matching string.