730. Count Different Palindromic Subsequences LeetCode Solution
In this guide, you will get 730. Count Different Palindromic Subsequences LeetCode Solution with the best time and space complexity. The solution to Count Different Palindromic Subsequences problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Count Different Palindromic Subsequences
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 109 + 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 109 + 7.
Constraints:
1 <= s.length <= 1000
s[i] is either 'a', 'b', 'c', or 'd'.
Complexity Analysis
Time Complexity: O(n^2)
Space Complexity: O(n^2)
730. Count Different Palindromic Subsequences LeetCode Solution in C++
class Solution {
public:
int countPalindromicSubsequences(string s) {
constexpr int kMod = 1'000'000'007;
const int n = s.length();
// dp[i][j] := the number of different non-empty palindromic subsequences in
// s[i..j]
vector<vector<long>> dp(n, vector<long>(n));
for (int i = 0; i < n; ++i)
dp[i][i] = 1;
for (int d = 1; d < n; ++d)
for (int i = 0; i + d < n; ++i) {
const int j = i + d;
if (s[i] == s[j]) {
int lo = i + 1;
int hi = j - 1;
while (lo <= hi && s[lo] != s[i])
++lo;
while (lo <= hi && s[hi] != s[i])
--hi;
if (lo > hi)
dp[i][j] = dp[i + 1][j - 1] * 2 + 2;
else if (lo == hi)
dp[i][j] = dp[i + 1][j - 1] * 2 + 1;
else
dp[i][j] = dp[i + 1][j - 1] * 2 - dp[lo + 1][hi - 1];
} else {
dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1];
}
dp[i][j] = (dp[i][j] + kMod) % kMod;
}
return dp[0][n - 1];
}
}; /* code provided by PROGIEZ */
730. Count Different Palindromic Subsequences LeetCode Solution in Java
class Solution {
public int countPalindromicSubsequences(String s) {
final int kMod = 1_000_000_007;
final int n = s.length();
// dp[i][j] := the number of different non-empty palindromic subsequences in
// s[i..j]
int[][] dp = new int[n][n];
for (int i = 0; i < n; ++i)
dp[i][i] = 1;
for (int d = 1; d < n; ++d)
for (int i = 0; i + d < n; ++i) {
final int j = i + d;
if (s.charAt(i) == s.charAt(j)) {
int lo = i + 1;
int hi = j - 1;
while (lo <= hi && s.charAt(lo) != s.charAt(i))
++lo;
while (lo <= hi && s.charAt(hi) != s.charAt(i))
--hi;
if (lo > hi)
dp[i][j] = dp[i + 1][j - 1] * 2 + 2;
else if (lo == hi)
dp[i][j] = dp[i + 1][j - 1] * 2 + 1;
else
dp[i][j] = dp[i + 1][j - 1] * 2 - dp[lo + 1][hi - 1];
} else {
dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1];
}
dp[i][j] = (int) ((dp[i][j] + kMod) % kMod);
}
return dp[0][n - 1];
}
} // code provided by PROGIEZ
730. Count Different Palindromic Subsequences LeetCode Solution in Python
class Solution:
def countPalindromicSubsequences(self, s: str) -> int:
kMod = 1_000_000_007
n = len(s)
# dp[i][j] := the number of different non-empty palindromic subsequences in
# s[i..j]
dp = [[0] * n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
for d in range(1, n):
for i in range(n - d):
j = i + d
if s[i] == s[j]:
lo = i + 1
hi = j - 1
while lo <= hi and s[lo] != s[i]:
lo += 1
while lo <= hi and s[hi] != s[i]:
hi -= 1
if lo > hi:
dp[i][j] = dp[i + 1][j - 1] * 2 + 2
elif lo == hi:
dp[i][j] = dp[i + 1][j - 1] * 2 + 1
else:
dp[i][j] = dp[i + 1][j - 1] * 2 - dp[lo + 1][hi - 1]
else:
dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1]
dp[i][j] = (dp[i][j] + kMod) % kMod
return dp[0][n - 1] # code by PROGIEZ
