Problem
Given a string s, return the number of different non-empty palindromic subsequences in s. Since the answer may be very large, return it modulo 10^9 + 7.
A subsequence of a string is obtained by deleting zero or more characters from the string.
A sequence is palindromic if it is equal to the sequence reversed.
Two sequences a1, a2, ... and b1, b2, ... are different if there is some i for which ai != bi.
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.
Constraints:
1 <= s.length <= 1000s[i]is either'a','b','c', or'd'.
Solution (Java)
class Solution {
public int countPalindromicSubsequences(String s) {
int big = 1000000007;
int len = s.length();
if (len < 2) {
return len;
}
int[][] dp = new int[len][len];
for (int i = 0; i < len; i++) {
char c = s.charAt(i);
int deta = 1;
dp[i][i] = 1;
int l2 = -1;
for (int j = i - 1; j >= 0; j--) {
if (s.charAt(j) == c) {
if (l2 < 0) {
l2 = j;
deta = dp[j + 1][i - 1] + 1;
} else {
deta = dp[j + 1][i - 1] - dp[j + 1][l2 - 1];
}
deta = deal(deta, big);
}
dp[j][i] = deal(dp[j][i - 1] + deta, big);
}
}
return deal(dp[0][len - 1], big);
}
private int deal(int x, int big) {
x %= big;
if (x < 0) {
x += big;
}
return x;
}
}
Solution (C++)
class Solution {
public:
int countPalindromicSubsequences(string S) {
static const int P = 1e9 + 7;
static const string chars = "abcd";
vector<vector<vector<int>>> dp(3, vector<vector<int>>(S.size(), vector<int>(4)));
for (int len = 1; len <= S.size(); ++len) {
for (int i = 0; i + len <= S.size(); ++i) {
for (const auto& c : chars) {
dp[len % 3][i][c - 'a'] = 0;
if (len == 1) {
dp[len % 3][i][c - 'a'] = S[i] == c;
} else {
if (S[i] != c) {
dp[len % 3][i][c - 'a'] = dp[(len - 1) % 3][i + 1][c - 'a'];
} else if (S[i + len - 1] != c) {
dp[len % 3][i][c - 'a'] = dp[(len - 1) % 3][i][c - 'a'];
} else {
dp[len % 3][i][c - 'a'] = 2;
if (len > 2) {
for (const auto& cc : chars) {
dp[len % 3][i][c - 'a'] += dp[(len - 2) % 3][i + 1][cc - 'a'];
dp[len % 3][i][c - 'a'] %= P;
}
}
}
}
}
}
}
int result = 0;
for (const auto& c : chars) {
result = (result + dp[S.size() % 3][0][c - 'a']) % P;
}
return result;
}
};
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).