Longest common sub-sequences with a condition

Question

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.

P.S - Problem link

Answer 1

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.