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[0][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[0][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[0][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[0][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[0][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[0][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]; 
       } 
   } 
   
   // return total palindromic subsequences 
   return dp[0][N-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]; }