Count Different Palindromic Subsequences - Leetcode Solution

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 10^9 + 7.

A subsequence of a string s is obtained by deleting zero or more characters from s. A sequence is palindromic if it reads the same forward and backward.

Two sequences a1, a2, …, ak and b1, b2, …, bk are different if there is some i such that ai ≠ bi.

Example:

Input: s = "bccb" Output: 6 Explanation: The 6 different non-empty palindromic subsequences are 'b', 'c', 'bb', 'cc', 'bcb', and 'bccb'.

Solution:

The problem asks us to count the different palindromic subsequences in a given string. We can solve the problem using dynamic programming. We will use a two-dimensional dp array to store our intermediate results. The dp[i][j] will store the number of palindromic subsequences that exist in the substring s[i..j] of the given string s.

We can fill the dp array using the following recurrence relation:

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

The idea behind this is that we can count all the palindromic subsequences that do not include the last character, all the palindromic subsequences that do not include the first character, and then subtract all the palindromic subsequences that do not include both the first and last character. This gives us the total count of palindromic subsequences that include at least one of the first and last character.

Now, to count the palindromic subsequences that include both the first and last character, we can traverse the string s and check for each character if it matches with the first and the last character. If it matches, then we can add 2 to our count (because we can choose to include or exclude the two matching characters).

We will also use a HashMap to keep track of the last occurrence of each character in the string s. This will help us avoid recomputing already computed values.

Finally, we will return the value stored in dp[0][n-1], where n is the length of the string s.

Here is the implementation of the above solution:

class Solution { public int countPalindromicSubsequences(String s) { int n = s.length(); int mod = (int)1e9 + 7; int[][] dp = new int[n][n]; HashMap<Character, Integer> last = new HashMap<>(); for (int i = n - 1; i >= 0; i--) { last.put(s.charAt(i), i); for (int j = i; j < n; j++) { if (i == j) { dp[i][j] = 1; } else if (s.charAt(i) != s.charAt(j)) { dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]; } else { int k = last.get(s.charAt(i)); if (k < j) { dp[i][j] = dp[i+1][j-1] * 2; if (k > i) { dp[i][j] -= dp[k-1][i+1]; } else { dp[i][j] += 1; } } else { dp[i][j] = dp[i+1][j-1] * 2 + 1; } } dp[i][j] = (dp[i][j] + mod) % mod; } } return dp[0][n-1]; } }

Time Complexity: O(n^2) where n is the length of the string s.

Space Complexity: O(n^2) for the dp array and O(n) for the HashMap.

1