Distinct Palindromic Subsequences

Hard

You are given a string text that contains only the letters a, b, c and d. A subsequence is what remains after deleting any characters (possibly none) without reordering the rest. A palindrome reads the same forwards and backwards. Count how many **distinct** non-empty palindromic strings can be obtained as a subsequence of text. The same string obtained by different deletions counts once. The answer can be huge, so return it modulo 10⁹ + 7.

Example 1

text="abca" → 6

The distinct palindromes are a, b, c, aa, aba, aca.

Example 2

text="dddd" → 4

There are many ways to pick dd, but it is one string. In total: d, dd, ddd, dddd.

Example 3

text="cabd" → 4

No letter repeats, so the only palindromes are the four single letters.

Constraints

1 ≤ len(text) ≤ 1000
text contains only the letters a, b, c, d

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Dynamic Programming

Similar problems

Pattern With Dot and Star Hard Longest Balanced Bracket Stretch Hard Does the Text Fit the Pattern Hard Shuffle by Cutting and Swapping Hard Ways to Cross Out Hard

Input

text="abca"

Expected

Run checks the first 3 tests in your browser. Submit checks all 82 tests on the server, hidden ones included.