# Solution For Count Palindromic Subsequences

Problem Statement:

Given a string s, return the number of palindromic subsequences in s. A subsequence is considered palindromic if it is the same whether read forwards or backwards.

A sequence is a palindromic sequence if the sequence, and the sequence reversed, are the same.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

A subsequence of S is any string which can be obtained by deleting zero or more characters from S.

Example:

Input: s = “bccb”
Output: 6
Explanation:
The 6 palindromic subsequences of s are:
– “b”, “c”, “bb”, “cc”, “bcb”, “bccb”.

Solution:

Approach:
To solve this problem, we can use dynamic programming. Let dp[i][j] be the count of distinct palindromic subsequences of s[i…j]. We can determine the value of dp[i][j] using the values of dp[i-1][j], dp[i][j-1], and dp[i-1][j-1].

We can start with dp[i][i] = 1 since a single character is a palindrome of length 1. If s[i] == s[j], then we can add 2 to the total count dp[i+1][j-1], since we can count the two subsequences s[i]+s[j] and s[i…j] as substrings of s[i…j]. We also need to account for the overlapping palindromic subsequences that we may have counted previously, so we subtract dp[i+1][j-1] with dp[i][j].

In the case where s[i] != s[j], we do not count any additional palindromic subsequences. Instead, we can determine the value of dp[i][j] using dp[i][j-1] and dp[i+1][j], since the subsequences of s[i…j-1] and s[i+1…j] are also palindromic subsequences of s[i…j]. We also need to subtract the overlapping palindromic subsequences dp[i+1][j-1] that we may have already counted, so we add dp[i+1][j-1] with dp[i][j-1]+dp[i+1][j].

We then return dp[n-1], where n is the length of the string s, which represents the count of all distinct palindromic subsequences of s.

Code:

int countSubstrings(string s) {
int n = s.length();
vector> dp(n, vector(n, 0));
for (int i = 0; i < n; i++) {
dp[i][i] = 1;
}
for (int len = 2; len <= n; len++) {
for (int i = 0; i <= n-len; i++) {
int j = i+len-1;
if (s[i] == s[j]) {
dp[i][j] = dp[i+1][j-1] + 1;
dp[i][j] -= (j > i+1) ? dp[i+1][j-1] : 0;
} else {
dp[i][j] = dp[i][j-1] + dp[i+1][j];
dp[i][j] -= (j > i+1) ? dp[i+1][j-1] : 0;
}
}
}
return dp[n-1];
}

Time Complexity: O(n^2)
Space Complexity: O(n^2)

Explanation:
We use a 2-D dp array of size nxn to store the count of distinct palindromic subsequences of s[i…j] from i to j. We then iterate through all possible lengths of palindromic subsequences starting from length 2, since all subsequences of length 1 are trivially palindromic. We then iterate through all possible starting indices i and ending indices j such that j <= i+len-1. For each i and j, we determine the count of palindromic subsequences using the approach described above, and we store the result in dp[i][j]. Finally, we return dp[n-1], where n is the length of the string s.

## Step by Step Implementation For Count Palindromic Subsequences

```public int countPalindromicSubsequences(String S) {
int n = S.length();
int[][] dp = new int[n][n];

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.charAt(i) == S.charAt(j)) {
int left = i + 1;
int right = j - 1;

while (left <= right && S.charAt(left) != S.charAt(i)) {
left++;
}

while (left <= right && S.charAt(right) != S.charAt(i)) {
right--;
}

if (left > right) {
dp[i][j] = dp[i + 1][j - 1] * 2 + 2;
} else if (left == right) {
dp[i][j] = dp[i + 1][j - 1] * 2 + 1;
} else {
dp[i][j] = dp[i + 1][j - 1] * 2 - 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] < 0 ? dp[i][j] + 1000000007 : dp[i][j] % 1000000007;
}
}

return dp[n - 1];
}```
```def countPalindromicSubsequences(S):

# Create a 2D array to store the results of subproblems

dp = [[0 for x in range(len(S))] for y in range(len(S))]

# Strings of length 1 are palindromic substrings

for i in range(len(S)):

dp[i][i] = 1

# Build the solution in a bottom-up fashion

for curr_len in range(2, len(S)+1):

for i in range(0, len(S)-curr_len+1):

j = i+curr_len-1

# If the first and the last characters are not same,

# then there is no palindrome

if S[i] != S[j]:

dp[i][j] = dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1]

# Else, then there are three possibilities

# 1: Whole string is palindrome

# 2: Nothing is palindrome

# 3: Some part of string is palindrome

else:

dp[i][j] = dp[i][j-1] + dp[i+1][j] + 1

# An empty substring is always a palindrome

return dp[len(S)-1]```
```var countPalindromicSubsequences = function(S) {
// create a 2D array of size S.length + 1 x S.length + 1
// to keep track of the number of palindromic subsequences
// for each substring of S
let dp = new Array(S.length + 1).fill(0).map(() => new Array(S.length + 1).fill(0));
// initialize the 2D array with all zeros

// every string has at least one palindromic subsequence,
// which is itself
for (let i = 0; i < S.length; i++) {
dp[i][i] = 1;
}

// consider substrings of length 2 to S.length
for (let len = 2; len <= S.length; len++) {
// for each substring of length len
for (let i = 0; i <= S.length - len; i++) {
let j = i + len - 1;
// if the first and last characters of the substring are the same,
// then we can add the number of palindromic subsequences of the
// substring S[i+1][j-1] to our count
if (S[i] === S[j]) {
dp[i][j] += dp[i+1][j-1] + 1;
} else {
// otherwise, we just take the sum of the number of
// palindromic subsequences of the substrings S[i][j-1] and S[i+1][j]
dp[i][j] += dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1];
}
// we need to mod by 1000000007 at each step because the number
// of palindromic subsequences can get very large very quickly,
// and we don't want it to overflow
dp[i][j] = dp[i][j] % 1000000007;
}
}

// return the number of palindromic subsequences of the entire string S
return dp[S.length - 1];
};```
```int countPS(string str)
{
int N = str.length();

// create a 2D array to store the count of
// palindromic subsequences
int dp[N][N];

// palindromes of length 1
for (int i = 0; i < N; i++)
dp[i][i] = 1;

// finding palindromes of length 2 to N
for (int curr_len = 2; curr_len <= N; curr_len++)
{
// for each position calculate the number
// of palindromes
for (int i = 0; i < N-curr_len+1; i++)
{
int j = i+curr_len-1;
if (str[i] == str[j] && curr_len == 2)
dp[i][j] = 2;
else if (str[i] == str[j])
dp[i][j] = dp[i+1][j] + dp[i][j-1] + 1;
else
dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1];
}
}

`public int CountPalindromicSubsequences(string s) { int n = s.Length; int[,] dp = new int[n, n]; // base case; a single letter is a palindrome for (int i = 0; i < n; i++) dp[i, i] = 1; // iterate over the length of the string for (int len = 1; len < n; len++) { // iterate over the start index of the string for (int i = 0; i < n - len; i++) { // calculate the end index int j = i + len; // if the first and last letter of the string are the same // we add the number of palindromic subsequences without // the first and last letter if (s[i] == s[j]) { dp[i, j] = dp[i + 1, j] + dp[i, j - 1] + 1; } // if the first and last letter of the string are not the same // we subtract the number of palindromic subsequences with // the first and last letter (which will be double counted) // and add the number of palindromic subsequences without // the first and last letter else { dp[i, j] = dp[i + 1, j] + dp[i, j - 1] - dp[i + 1, j - 1]; } } } return dp[0, n - 1]; }`