Count Palindromic Subsequences - Leetcode Solution

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<vector<int>> dp(n, vector<int>(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.

1