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
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]; }