## 730. Count Different Palindromic Subsequences

Given a string S, find the number of different non-empty palindromic subsequences in S, and return that number modulo `10^9 + 7`.

A subsequence of a string S is obtained by deleting 0 or more characters from S.

A sequence is palindromic if it is equal to the sequence reversed.

Two sequences `A_1, A_2, ...` and `B_1, B_2, ...` are different if there is some `i` for which `A_i != B_i`.

Example 1:

```Input:
S = 'bccb'
Output: 6
Explanation:
The 6 different non-empty palindromic subsequences are 'b', 'c', 'bb', 'cc', 'bcb', 'bccb'.
Note that 'bcb' is counted only once, even though it occurs twice.
```

Example 2:

```Input:
Output: 104860361
Explanation:
There are 3104860382 different non-empty palindromic subsequences, which is 104860361 modulo 10^9 + 7.
```

Note:

• The length of `S` will be in the range `[1, 1000]`.
• Each character `S[i]` will be in the set `{'a', 'b', 'c', 'd'}`.

• b'
\n\n

#### Approach #1 Dynamic Programming (using 3D array) [Accepted]

\n

Intuition and Algorithm

\n

Let `dp[x][i][j]` be the answer for the substring `S[i...j]` where\n`S[i] == S[j] == \'a\'+x`. Note that since we only have 4 characters `a,\nb, c, d`, thus `0 <= x < 4`. The DP formula goes as follows:

\n
\n
• \n

If `S[i] != \'a\'+x`, then `dp[x][i][j] = dp[x][i+1][j]`, note that\n here we leave the first character `S[i]` in the window out due to\n our definition of `dp[x][i][j]`.

\n
• \n
• \n

If `S[j] != \'a\'+x`, then `dp[x][i][j] = dp[x][i][j-1]`, leaving the\n last character `S[j]` out.

\n
• \n
• \n

If `S[i] == S[j] == \'a\'+x`, then `dp[x][i][j] = 2 +\n dp[0][i+1][j-1] + dp[1][i+1][j-1] + dp[2][i+1][j-1] +\n dp[3][i+1][j-1]`. When the first and last characters are the same, we\n need to count all the distinct palindromes (for each of `a,b,c,d`) within\n the sub-window `S[i+1][j-1]` plus the `2` palindromes contributed by\n the first and last characters.

\n
• \n
\n

Let `n` be the length of the input string `S`, The final answer would\nbe `dp[0][0][n-1] + dp[1][0][n-1] + dp[2][0][n-1] + dp[3][0][n-1]`\nmod `1000000007`.

\n\n

Example Walkthrough

\n

Indeed this is a hard problem to solve and thoroughly understanding\nits solution is also challenging. Maybe the best way to understand the\nabove approach is to walkthrough some simple examples to help build up\nintuitions.

\n

Let\'s first look at the strategy we used to fill the DP table and then walkthrough a concrete example to see how it works.

\n

\n

!?!../Documents/730_Example_Walkthrough.json:1280,720!?!

\n

Complexity Analysis

\n
\n
• \n

Time complexity : where is the length of the input\n string . It takes quadratic time to fill up the DP table.

\n
• \n
• \n

Space complexity : where is the length of the input\n string . The DP table takes quadratic space.

\n
• \n
\n

Note that we ignore the constant factor in the above analysis.

\n

Conclusion

\n

As we look back, this problem reveals a key attribute which indicates\nthat dynamic programming might be a good fit: `overlapping\nsub-problems` as we recall the DP formula. By practicing more\nproblems, we can build up this kind of intuition.

\n

Credit: the above solution is inspired by\nthis post\nwritten by @elastico. His solution is space optimized. However, I found\nthat my approach is relatively easy to understand for people who found\nthis problem hard to approach.

\n
\n

Analysis written by: @imsure.

\n

#### Approach #2: Dynamic Programming (using 2D array) [Accepted]

\n

Intuition

\n

Almost every palindrome is going to take one of these four forms: `a_a`, `b_b`, `c_c`, or `d_d`, where `_` represents a palindrome of zero or more characters. (The only other palindromes are `a`, `b`, `c`, `d`, and the empty string.)

\n

Let\'s try to count palindromes of the form `a_a` - the other types are similar. Evidently, we should take the first and last `a`, then count all the palindromes that can be formed in between, as this provides us strictly more possibilities for `_` to be a palindrome. This reveals an optimal substructure that is ideal for dynamic programming.

\n

Algorithm

\n

Let `dp(i, j)` be the number of palindromes (including the palindrome `\'\'`) in the string `T = S[i], S[i+1], ..., S[j]`. To count palindromes in `T` of the form `a_a`, we will need to know the first and last occurrence of `\'a\'` in this string. This can be done by a precomputed dp: `next[i][0]` will be the next occurrence of `\'a\'` in `S[i:]`, `next[i][1]` will be the next occurrence of `\'b\'` in `S[i:]`, and so on.

\n

Also, we will need to know the number of unique letters in `T` to count the single letter palindromes. We can use the information from `next` to deduce it: if `next[i][0]` is in the interval `[i, j]`, then `\'a\'` occurs in `T`, and so on.

\n

As many states `dp(i, j)` do not need to be computed, the most natural approach is a top-down variation of dynamic programming.

\n\n

Complexity Analysis

\n
\n
• \n

Time Complexity: , where is the size of the string `S`. Our calculation of `prv` and `nxt` happens in time, then our evaluation of `dp` with at most states is work per state.

\n
• \n
• \n

Space Complexity: , the size of `memo`.

\n
• \n
\n
\n

Analysis written by: @awice.

\n
'