Last updated on January 29th, 2025 at 02:12 am
Here, we see a Count Different Palindromic Subsequences LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Dynamic Programming, String
Companies
Level of Question
Hard
Count Different Palindromic Subsequences LeetCode Solution
Table of Contents
1. Problem Statement
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.
2. Coding Pattern Used in Solution
The coding pattern used in the provided code is “Palindromic Subsequence”. This pattern involves dynamic programming to solve problems related to counting or finding palindromic subsequences in a string. The problem is solved by breaking it into smaller subproblems and using overlapping subproblems to optimize the solution.
3. Code Implementation in Different Languages
3.1 Count Different Palindromic Subsequences C++
class Solution {
public:
int countPalindromicSubsequences(string s) {
int n = s.size() ;
long long mod = 1000000007 ;
vector<int>next(n) , prev(n) ;
map<char,int>m ;
for(int i = 0 ; i<n ; i++)
{
char ch = s[i] ;
if(m[ch])
{
prev[i] = m[ch] - 1 ;
m[ch] = i + 1 ;
}
else
{
m[ch] = i+1 ;
prev[i] = -1 ;
}
}
m.clear() ;
for(int i = n-1 ; i>=0 ; i--)
{
char ch = s[i] ;
if(m[ch])
{
next[i] = m[ch] - 1 ;
m[ch] = i + 1 ;
}
else
{
m[ch] = i + 1 ;
next[i] = -1 ;
}
}
vector<vector<long long>>dp(n , vector<long long>(n , 0)) ;
int i = 0 ;
int j = 0 ;
int lastcol = 0 ;
while(1)
{
while(i < n && j < n)
{
int gap = j - i ;
if(gap == 0) dp[i][j] = 1 % mod ;
else if(gap == 1) dp[i][j] = 2 % mod ;
else
{
if(s[i] != s[j]) dp[i][j] = (dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1]) % mod ;
else
{
if(next[i] == j && prev[j] == i) dp[i][j] = (2 * dp[i+1][j-1] + 2) % mod ;
else if(next[i] == prev[j]) dp[i][j] = (2 * dp[i+1][j-1] + 1) % mod ;
else dp[i][j] = (2 * dp[i+1][j-1] - dp[next[i] + 1][prev[j] - 1]) % mod ;
}
}
i++ ;
j++ ;
}
if(lastcol == n-1) break ;
i = 0 ;
j = lastcol + 1 ;
lastcol = j ;
}
if(dp[0][n-1] < 0) dp[0][n-1] += mod ;
return dp[0][n-1] ;
}
};
3.2 Count Different Palindromic Subsequences Java
class Solution {
public int countPalindromicSubsequences(String s) {
int n = s.length();
char[] c = s.toCharArray();
int[] prev = new int[n];
int[] next = new int[n];
HashMap<Character,Integer> map = new HashMap();
for(int i=0;i<n;i++){
if(map.containsKey(c[i])) prev[i]=map.get(c[i]);
else prev[i]=-1;
map.put(c[i],i);
}
map.clear();
for(int i=n-1;i>=0;i--){
if(map.containsKey(c[i])) next[i]=map.get(c[i]);
else next[i]=-1;
map.put(c[i],i);
}
int[][] dp = new int[n][n];
int mod=(int)1e9+7;
for(int g=0;g<n;g++){
for(int i=0,j=g;j<n;i++,j++){
if(g==0) dp[i][j]=1;
else if(g==1) dp[i][j]=2;
else if(c[i]==c[j]) {
int li = next[i], ri=prev[j];
if(li==j&&ri==i) dp[i][j] = (2*dp[i+1][j-1])%mod+2;
else if(li==ri) dp[i][j] = (2*dp[i+1][j-1])%mod+1;
else dp[i][j] = ((2*dp[i+1][j-1])%mod - dp[li+1][ri-1] + mod)%mod;
}
else dp[i][j] = ((dp[i+1][j]%mod + dp[i][j-1]%mod)%mod -
dp[i+1][j-1] + mod)%mod;
}
}
return dp[0][n-1];
}
}
3.3 Count Different Palindromic Subsequences JavaScript
var countPalindromicSubsequences = function (s) {
let len = s.length;
let dp = new Array(len).fill(0).map(() => new Array(len).fill(0));
let mod = (10 ** 9) + 7;
for (let i = 0; i < len; i++) dp[i][i] = 1;
for (let i = len - 1; i > -1; i--) {
for (let j = i + 1; j < len; j++) {
if (s[i] === s[j]) {
let left = i + 1;
let right = j - 1;
while (left <= right && s[i] !== s[left]) left++;
while (left <= right && s[i] !== s[right]) right--;
if (left > right) dp[i][j] = (2 * dp[i + 1][j - 1]) + 2;
else if (left === right) dp[i][j] = (2 * dp[i + 1][j - 1]) + 1;
else dp[i][j] = (2 * dp[i + 1][j - 1]) - dp[left + 1][right - 1];
} else {
dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1];
}
dp[i][j] = ((dp[i][j] + mod) % mod);
}
}
return dp[0][len - 1];
};
3.4 Count Different Palindromic Subsequences Python
class Solution(object):
def countPalindromicSubsequences(self, s):
memo = {}
def dfs(i,j):
if i > j: return 0
if i == j: return 1
if (i,j) in memo: return memo[(i,j)]
count = 0
if s[i] == s[j]:
count = 2*dfs(i+1,j-1)
left, right = i+1, j-1
while left <= right and s[i] != s[left]: left += 1
while right >= left and s[i] != s[right]: right -= 1
# Remoce Duplicate Palindromes
if left < right: count -= dfs(left+1, right-1)
elif left == right: count += 1
else: count += 2
else:
count = dfs(i+1,j) + dfs(i,j-1) - dfs(i+1,j-1)
memo[(i,j)] = count % 1000000007
return memo[(i,j)]
return dfs(0,len(s)-1)
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n2) | O(n2) |
| Java | O(n2) | O(n2) |
| JavaScript | O(n2) | O(n2) |
| Python | O(n3) | O(n2) |