1
$\begingroup$

Taking a sequence, I am looking to calculate the minimum amount of continuous palindromic subsequences to build up such a sequence. I believe the best way is using a recursive DP algorithm.

I am having trouble picturing the problem space or the most efficient way to do it. (For example, is it best to find the longest palindromic continuous subsequence first, or rather find the earliest one first?)

For example:

Sequence: [A, C, C, C, A, B, Y, B] is made up from 2 subsequences, namely [A, C, C, C, A], [B, Y, B]

So, therefore, my output for this example would be 2.

Thanks in advance!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Let $S$ be your input sequence and denote by $S[i:j]$ the subsequence going from the $i$-th to the $j$-th element of $S$ (inclusive).

Let $OPT[i]$ be the minimum amount of continuous palindromic subsequences in which $S[1:i]$ can be partitioned. Let $OPT[0]=0$. For $j=1,\dots,|S|$, you have:

$$ OPT[j] = \min_{\substack{i=1,\dots,j\\S[i:j] \text{ is a palindrome}}} \{1+ OPT[i-1] \}. $$

The value you are looking for is $OPT[|S|]$. This algorithm requires time $O(|S|^2)$. Notice that all the pairs $(i,j)$ for which $S[i:j]$ is palindrome can be precomputed in $O(|S|^2)$ time.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ The recursive formula is exactly the one I wrote in my answer. The base case is $OPT[0]$. That is, the minimum number of subsequences needed to partition $S[1:0]$ (the empty subsequence) into palindromes, which is 0. If you don't like this edge case, then you can define $OPT[1]=1$ as your base case and modify the recursive formula slightly to account for this. $\endgroup$ Commented Apr 26, 2020 at 3:24
  • $\begingroup$ Thanks @Steven - what adjustment would I need to make to the recursive formula if my base case was $OPT[1] = 1$. Would it just mean that $i=2,...,j$? $\endgroup$ Commented Apr 26, 2020 at 3:36
  • 1
    $\begingroup$ No, that won't be enough because you would not be considering the case where $S[1:j]$ is a palindrome. The formula would be: $OPT[j] = \begin{cases} 1 & \text{if $S[1:j]$ is a palindrome} \\ \min_{\substack{i=1,\dots,j}\\ S[i:j]\text{ is a palindrome}} \{ 1+ OPT[i-1] \} & \text{otherwise} \end{cases}$. Using $S[1:0]$ as a base case, avoids the need to distinguish these two cases. Also notice that there is no need to take the minimum between $1$ and the $\min ...$ formula in the first of the two cases since, for $j \ge 1$, $OPT[j]$ must be at least $1$. $\endgroup$ Commented Apr 26, 2020 at 3:39

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.