# Longest common sub-sequences with a condition

A sequence is called good if it contains at least one pair of numbers which are adjacent and equal. A good sub-sequence of an array is a sub-sequence of that array which is good and has maximal length.
Now you are given two arrays $$S$$ and $$T$$ with integers. You need to find a sub-sequence which is common to both arrays, has maximum length, and is a good sub sequence.

This is a pure dynamic programming problem, in which states ( I am not sure,but is is my guess) are $$dp[i][j]$$ is answer for $$S[1:i]$$ and $$T[1:j]$$ ($$A[1:i]$$ means subarray of $$A$$ from $$1$$ to $$i$$). But I could not find transition between states, could anyone help me.

• How do you know that the algorithm has states of the given form?
– D.W.
Sep 15 '20 at 6:44
• @D.W. It appeared trivial to me,there might be extra state i might be missing.
– nope
Sep 15 '20 at 9:26
• I think you are making a faulty assumption, and you should broaden your perspective on what the states might look like... especially since you could not find a recursive relation with those states.
– D.W.
Sep 15 '20 at 16:27
• @D.W. Can you give hint for states ?
– nope
Sep 15 '20 at 16:30
• cs.stackexchange.com/tags/dynamic-programming/info
– D.W.
Sep 15 '20 at 17:04

A two-dimensional $$dp[i][j]$$ is not fine enough to enable a recurrence relation. We need to track more information to be able to find the solutions to larger problems from the solutions of smaller problems.

Instead of $$dp[i][j]$$, try filling the following two tables simultaneously

• $$dp\_good[i][j]$$, which means the length of longest common good subsequence of $$S[1:i]$$ and $$T[1:j]$$ that ends at $$S[i]$$ and $$T[j]$$. This number is $$0$$ is $$S[i]\not=T[j]$$.
• $$dp\_bad[i][j]$$, which means the length of longest common bad subsequence of $$S[1:i]$$ and $$T[1:j]$$ that ends at $$S[i]$$ and $$T[j]$$. Here a bad subsequence just means it is not a good subsequence. Again, this number is $$0$$ is $$S[i]\not=T[j]$$.

The answer will be the maximum of all $$dp\_good[i][j]$$.

The above approach should work when you are looking for a sequence that "contains at least one pair of numbers which are adjacent and equal."

For the original problem, Task: ZAJ Stutter, we should define a good string as a stutter, i.e., a string that consists of successive pairs of two equal elements. A bad string will be defined as "almost a stutter", that is, a strings which becomes a stutter if we delete its last element.

• More techniques are needed to solve that original problem within a second or two if, for example, $n=m=15000$. Sep 15 '20 at 19:38