Solution For Count Different Palindromic Subsequences
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
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.
Step by Step Implementation For Count Different Palindromic Subsequences
class Solution {
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; // String of length 1 is always a palindrome
}
for (int len = 2; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
char c1 = S.charAt(i), c2 = S.charAt(j);
if (c1 == c2) {
int low = i + 1, high = j - 1;
/* If there are characters between c1 and c2 and none of
* these characters is equal to c1 or c2, then we get
* dp[i][j] by removing one character from either ends */
while (low <= high && S.charAt(low) != c1) {
low++;
}
while (low <= high && S.charAt(high) != c1) {
high--;
}
/* If there are only one character between c1 and c2 or if
* there are no characters between c1 and c2 and c1 != c2,
* then we get dp[i][j] by removing one character from either
* ends */
if (low > high) {
dp[i][j] = dp[i+1][j-1] * 2 + 2;
}
/* If there are more than one character between c1 and c2 and
* all of these characters are equal to c1 or c2, then we
* get dp[i][j] by removing one character from either ends */
else if (low == high) {
dp[i][j] = dp[i+1][j-1] * 2 + 1;
}
/* If there are more than one character between c1 and c2 and
* not all of these characters are equal to c1 or c2, then
* we get dp[i][j] by removing one character from either ends */
else {
dp[i][j] = dp[i+1][j-1] * 2 - dp[low+1][high-1];
}
}
else {
dp[i][j] = dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1]; // S[i] != S[j]
}
dp[i][j] = dp[i][j] < 0 ? dp[i][j] + 1000000007 : dp[i][j] % 1000000007;
}
}
return dp[0][n-1];
}
}class Solution:
def countPalindromicSubsequences(self, S: str) -> int:
# Base cases
if len(S) == 0:
return 0
if len(S) == 1:
return 1
# Create a 2D array of size len(S) x len(S) to
# store the subproblem solutions
dp = [[0 for i in range(len(S))] for j in range(len(S))]
# Fill the array in diagonal fashion (i.e. for substrings
# of length 1, then length 2, and so on)
for i in range(len(S)):
dp[i][i] = 1 # length 1 is always a palindrome
for l in range(2, len(S)+1):
for i in range(len(S)-l+1):
j = i+l-1
if S[i] == S[j]:
# If the first and last characters match, we
# need to consider 2 cases:
# 1. The rest of the string is a palindrome
# 2. The rest of the string is NOT a palindrome
#
# In case 1, we simply add 2 to the solution for
# the subproblem (i+1, j-1), since we know that
# the first and last characters form a palindrome
# and the rest of the string is a palindrome
#
# In case 2, we need to consider all possible
# substrings that start and end with the same
# character (but are not necessarily palindromes).
# We can do this by iterating over all characters
# between i and j (both inclusive) and checking
# if they are equal to S[i]. If they are, we add
# the number of substrings that start and end
# with that character to our solution. Note that
# we need to subtract 2 from this number, since
# we do not want to count the substring (i,j)
# twice.
dp[i][j] = dp[i+1][j-1] * 2
for k in range(i+1, j):
if S[k] == S[i]:
dp[i][j] += dp[i+1][k-1]
break
else:
# If the first and last characters do not match,
# we simply add the solutions to the subproblems
# (i+1,j) and (i,j-1)
dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]
return dp[0][len(S)-1]//Solution:
var countDifferentPalindromicSubsequences = function(S) {
//Create a set to store all the unique palindromic subsequences
let set = new Set();
//Loop through the string
for(let i = 0; i < S.length; i++){
//For each character, find all the palindromes that include that character
findPalindromes(S, i, i, set); //Odd length palindromes
findPalindromes(S, i, i+1, set); //Even length palindromes
}
//Return the size of the set - this will be the number of unique palindromic subsequences
return set.size;
};
var findPalindromes = function(str, left, right, set){
//Loop while the left and right indices are within the string bounds and the characters at those indices are equal
while(left >= 0 && right < str.length && str.charAt(left) === str.charAt(right)){
//Add the palindrome to the set
set.add(str.substring(left, right+1));
//Move the left and right indices inward
left--;
right++;
}
}class Solution {
public:
int countPalindromicSubsequences(string S) {
int n = S.size();
vector> dp(n, vector(n));
unordered_map> m;
for (int i = 0; i < n; ++i) {
m[S[i]].push_back(i);
dp[i][i] = 1;
}
for (int i = n - 1; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
if (S[i] == S[j]) {
int left = m[S[i]].front();
int right = m[S[i]].back();
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 + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1];
}
dp[i][j] = (dp[i][j] + MOD) % MOD;
}
}
return dp[0][n - 1];
}
private:
const int MOD = 1e9 + 7;
}; using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
string s = "bccb";
Console.WriteLine(CountPalindromicSubsequences(s));
Console.ReadKey();
}
// Function to count the total number of
// palindromic subsequences in a given string
static int CountPalindromicSubsequences(string s)
{
int N = s.Length;
// dp[i][j] stores the count of palindromic
// subsequences in substring s[i..j]
int[][] dp = new int[N][];
for (int i = 0; i < N; i++)
dp[i] = new int[N];
// Strings of length 1 are palindrome of length 1
for (int i = 0; i < N; i++)
dp[i][i] = 1;
// Build the solution in bottom up manner by
// considering all substrings of length starting
// from 2 to N.
for (int cur_len = 2; cur_len <= N; cur_len++)
{
for (int i = 0; i < N - cur_len + 1; i++)
{
int j = i + cur_len - 1;
// If the first and last characters are not same
// then the substrings is not a palindrome
if (s[i] != s[j])
dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1];
else
{
// Else if the first and last characters are same
int low = i + 1, high = j - 1;
// Find the first and last characters in the
// substring s[i+1...j-1] that are same as s[i]
while (low <= high && s[low] != s[i])
low++;
while (low <= high && s[high] != s[i])
high--;
// If the first and last characters of the
// substring are same as s[i], then add 1
// to the solution and remove the common
// palindromic subsequences from the left
// and right side of the current subsequence
if (low > high)
dp[i][j] = 2 * dp[i + 1][j - 1] + 1;
else
{
// This case is handled when the
// substring contains only 2 characters
if (low == high)
dp[i][j] = 2 * dp[i + 1][j - 1] + 1;
// This case is handled when the
// substring contains more than 2
// characters
else
dp[i][j] = 2 * dp[i + 1][j - 1] - dp[low + 1][high - 1];
}
}
}
}
// Return the total count of all the
// palindromic subsequences
return dp[0][N - 1];
}
}
}