Last updated on October 9th, 2024 at 05:43 pm
Here, We see Count Different Palindromic Subsequences LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
Topics
Dynamic Programming, String
Companies
Level of Question
Hard
Count Different Palindromic Subsequences LeetCode Solution
Table of Contents
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.
1. Count Different Palindromic Subsequences LeetCode Solution 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] ;
}
};2. Count Different Palindromic Subsequences LeetCode Solution 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. Count Different Palindromic Subsequences LeetCode Solution 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];
};4. Count Different Palindromic Subsequences Solution 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)