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:
S = 'abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba'
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'}.
// Top-Down Dynamic Programming with Memoization
int helper(const string& S, const vector<vector<int> >& chars, int start, int end, vector<vector<int> >& memo) {
if (start >= end) return 0;
if (memo[start][end] > 0) return memo[start][end];
long res = 0;
for (int i = 0; i < 26; ++i) {
if (chars[i].empty()) continue;
auto new_start = lower_bound(chars[i].begin(), chars[i].end(), start);
auto new_end = lower_bound(chars[i].begin(), chars[i].end(), end) - 1;
if (new_start == chars[i].end() || *new_start >= end) continue;
++res; // new_start exists => single char can be counted, e.g. "a"
if (new_start != new_end) ++res; // double char can be counted, e.g. "aa"
res += helper(S, chars, *new_start + 1, *new_end, memo);
}
return memo[start][end] = res % (int)(1e9 + 7);
}
int countPalindromicSubsequences(string S) {
int n = S.length();
vector<vector<int> > chars(26, vector<int>()), memo(n + 1, vector<int>(n + 1, 0));
for (int i = 0; i < n; ++i) {
chars[S[i] - 'a'].emplace_back(i);
}
return helper(S, chars, 0, n, memo);
}
// Bottom-Up Dynamic Programming
int countPalindromicSubsequences(string S) { // time: O(n^3); space: O(n^2)
int n = S.size(), M = 1e9 + 7;
vector<vector<int> > dp(n, vector<int>(n, 0));
for (int i = 0; i < n; ++i) dp[i][i] = 1;
for (int len = 1; len < n; ++len) {
for (int i = 0; i < n - len; ++i) {
int j = i + len;
if (S[i] == S[j]) {
int low = i + 1, high = j - 1;
while (low <= high && S[low] != S[i]) ++low;
while (low <= high && S[high] != S[j]) --high;
if (low > high) dp[i][j] = dp[i + 1][j - 1] * 2 + 2; // a...a, e.g. aba
else if (low == high) dp[i][j] = dp[i + 1][j - 1] * 2 + 1; // a...a...a, e.g. aaa
else dp[i][j] = dp[i + 1][j - 1] * 2 - dp[low + 1][high - 1]; // a...a...a...a, e.g. aacaa
} else {
dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1];
}
dp[i][j] = (dp[i][j] < 0) ? dp[i][j] + M : dp[i][j] % M;
}
}
return dp[0][n - 1];
}