730. Count Different Palindromic Subsequences
Problem Description
The problem requests to find the number of unique non-empty palindromic subsequences within a given string s. 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 palindromic sequence is one that reads the same backward as forward. Unique subsequences mean that they differ from each other by at least one element at some position.
The answer could be very large, so it is required to return the result modulo 10^9 + 7. This is a common practice in many problems to avoid very large numbers that can cause arithmetic overflow or that are outside the range of standard data type variables.
A key point to remember is that characters can be deleted to form subsequences; they don't have to be contiguous in the original string. Also, since subsequences are not required to be substrings; their characters can be dispersed throughout the string.
Intuition
The solution to this problem is based on dynamic programming. The main idea is to use a 3-dimensional array dp, where dp[i][j][k] represents the count of palindromic subsequences of type k in the substring s[i:j+1]. Here, i and j are the start and end indices of the substring, and k refers to the different characters (since this is limited to 4 different characters 'a', 'b', 'c', 'd', the third dimension has a size of 4).
The approach iterates over all substrings of s, and for each substring and each character type 'a' to 'd':
-
If both ends of the substring
iandjhave the same characterc, then the palindrome count for this character indp[i][j][k]includes all the palindromes withins[i+1: j-1]plus 2 (for the subsequences made by the single charactercand the one formed bycc). -
If only one end has the character
c, then the palindrome count for this character indp[i][j][k]is the same as in the substrings[i: j]ors[i+1: j+1], depending on which end has the characterc. -
If neither end has the character
c, then the count remains the same as in the substrings[i+1: j-1].
After filling the dp array, we sum up the counts for all types of characters at the first and last position dp[0][n-1], where n is the length of the string and take modulo 10^9 + 7 for the final answer.
This method ensures that all possible unique palindromic subsequences are counted without duplication, as the dynamic programming array stores the results of previous computations and avoids re-calculating them.
Learn more about Dynamic Programming patterns.
What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)
Solution Approach
The given Python solution implements a dynamic programming approach to solve the problem efficiently.
Breaking down the implementation we have:
-
Initialization: The solution creates a 3-dimensional list (or array)
dpwhich is initialized to hold all zeros. The dimensions ofdpare[n][n][4], wherenis the length of the string and4represents the four possible characters ('a', 'b', 'c', 'd'). -
Base Case: For each character in the input string
s, we setdp[i][i][ord(c) - ord('a')] = 1. This means that for every character in the string, there is exactly one palindromic subsequence of length 1. -
Main Loop: The solution then iterates over all possible lengths of substrings
lstarting from2up toninclusive. For each length, it loops over all possible starting indicesiof the substring. -
State Transitions:
- If the characters at both ends are the same and are the character
c, the countdp[i][j][k]is calculated by adding2(accounting for the subsequences made by the single character and the one formed by two characters) plus the sum of counts of all palindromic subsequences within the substring (ignoring the two ends). This is represented bysum(dp[i + 1][j - 1]). - If only one of the ends matches the character
c, the count should be the same as the count of palindromic subsequences ending before the unmatched character. - If neither of the ends is the character
c, we fall back to the count for the smaller substring inside the current substring.
- If the characters at both ends are the same and are the character
-
Modular Arithmetic: As the answer can be very large, every time we calculate the sum, we take modulo
10^9 + 7to keep the number within the integer range. -
Final Answer: After populating the
dparray, the answer is the sum ofdp[0][n - 1](representing counts of different palindromic subsequences in the entire string from the first to the last character) modulo10^9 + 7.
The key data structure used here is the 3D list which holds counts of palindromic subsequences for all substrings and for each character type. The algorithm utilizes dynamic programming by breaking down the problem into smaller subproblems and uses previously computed values to calculate the larger ones, thus optimizing the number of computations required.
Which of the following problems can be solved with backtracking (select multiple)
Example Walkthrough
Let's consider a small example to illustrate the solution approach. Take the string s = "abca".
-
Initialization: We create a 3D array
dpof size[4][4][4], as the string lengthnis 4. This array will hold zeros initially. -
Base Case: We iterate over each character in
s. Fori = 0...3(string indices):dp[0][0][0] = 1(for 'a')dp[1][1][1] = 1(for 'b')dp[2][2][2] = 1(for 'c')dp[3][3][0] = 1(for 'a')
In each case, we're adding 1 for a single-character palindrome subsequence.
-
Main Loop: We loop through all possible substring lengths
l = 2...4. In this case, let's look atl = 2. We loop over all start indicesifor this length.- For
l = 2, substringab(s[0:2]), we havei = 0:- The characters at
s[0]ands[1]are different, so for character 'a',dp[0][1][0] = dp[0][0][0] = 1. - For character 'b',
dp[0][1][1] = dp[1][1][1] = 1.
- The characters at
- For
-
State Transitions: For
l = 2, continue with the state transitions:- Look at substring
bc(s[1:3]), wherei = 1:- Characters at
s[1]ands[2]are different, sodp[1][2][1] = dp[1][1][1] = 1, anddp[1][2][2] = dp[2][2][2] = 1.
- Characters at
- Look at substring
-
Continue Looping: Continue with
l = 3and thenl = 4, updating thedparray based on the rules defined in the solution approach.For example, if we check for
l = 3:- Substring
abc(s[0:3]), since both ends are different,dp[0][2][0] = dp[1][1][0]anddp[0][2][1] = dp[1][1][1].
- Substring
-
Final Answer: After populating the
dparray for all substrings of all lengths, our answer would be the sumsum(dp[0][3])modulo10^9 + 7for the full string length (from the first to the last character).
For our example string s = "abca", the unique palindromic subsequences are 'a', 'b', 'c', 'aa', 'aca'. The count is 5 which is the sum we expect at dp[0][3] before taking the modulo. Note that in reality, the dp array would hold more data points and aggregating them would include performing modulo operations to keep within numeric limits.
Solution Implementation
1class Solution:
2 def countPalindromicSubsequences(self, string: str) -> int:
3 # Define the modulus to ensure the return value is within the expected range.
4 MOD = 10**9 + 7
5
6 # Get the length of the string to iterate through it.
7 length = len(string)
8
9 # Initialize a 3D array to store the count of palindromic subsequences.
10 # dp[i][j][k] will store the count for the substring string[i:j+1] with character 'abcd'[k].
11 dp = [[[0] * 4 for _ in range(length)] for _ in range(length)]
12
13 # Base case initialization for substrings of length 1.
14 for index, character in enumerate(string):
15 dp[index][index][ord(character) - ord('a')] = 1
16
17 # Starting from substrings of length 2, build up solutions for longer substrings.
18 for substring_length in range(2, length + 1):
19 for start in range(length - substring_length + 1):
20 end = start + substring_length - 1
21 for char in 'abcd':
22 char_index = ord(char) - ord('a')
23 # If the current characters at start and end indices match and match 'char',
24 # count the inner subsequences twice (for including both start and end characters,
25 # and excluding both), and add the counts of all subsequences in between.
26 if string[start] == string[end] == char:
27 dp[start][end][char_index] = (2 + sum(dp[start + 1][end - 1])) % MOD
28 # If only the start character matches 'char', carry over the count from the previous.
29 elif string[start] == char:
30 dp[start][end][char_index] = dp[start][end - 1][char_index]
31 # If only the end character matches 'char', carry over the count from the previous.
32 elif string[end] == char:
33 dp[start][end][char_index] = dp[start + 1][end][char_index]
34 # If neither character matches 'char', the count remains the same as the inner substring.
35 else:
36 dp[start][end][char_index] = dp[start + 1][end - 1][char_index]
37
38 # Finally, sum up all the counts for the entire string and each character 'abcd',
39 # and apply the modulus for the result.
40 return sum(dp[0][length - 1]) % MOD
411class Solution {
2 // Define the modulus constant for the problem
3 private static final int MOD = 1_000_000_007;
4
5 public int countPalindromicSubsequences(String s) {
6 int n = s.length(); // Length of the string
7
8 // 3D dynamic programming array to store results
9 long[][][] dp = new long[n][n][4];
10
11 // Base case: single character strings
12 for (int i = 0; i < n; ++i) {
13 dp[i][i][s.charAt(i) - 'a'] = 1;
14 }
15
16 // Loop over all possible substring lengths
17 for (int len = 2; len <= n; ++len) {
18 // Iterate over all possible starting points for substring
19 for (int start = 0; start + len <= n; ++start) {
20 int end = start + len - 1; // Calculate end index of substring
21 // Try for each character a, b, c, d
22 for (char c = 'a'; c <= 'd'; ++c) {
23 int charIndex = c - 'a'; // Convert char to index (0 to 3)
24 // Case 1: Characters at both ends match the current character
25 if (s.charAt(start) == c && s.charAt(end) == c) {
26 // Count is sum of inner substring counts + 2 (for the two characters added)
27 dp[start][end][charIndex] = 2 + dp[start + 1][end - 1][0]
28 + dp[start + 1][end - 1][1] + dp[start + 1][end - 1][2]
29 + dp[start + 1][end - 1][3];
30 dp[start][end][charIndex] %= MOD; // Ensure mod operation
31 }
32 // Case 2: Only the start character matches
33 else if (s.charAt(start) == c) {
34 dp[start][end][charIndex] = dp[start][end - 1][charIndex];
35 }
36 // Case 3: Only the end character matches
37 else if (s.charAt(end) == c) {
38 dp[start][end][charIndex] = dp[start + 1][end][charIndex];
39 }
40 // Case 4: Neither end matches the character
41 else {
42 dp[start][end][charIndex] = dp[start + 1][end - 1][charIndex];
43 }
44 }
45 }
46 }
47
48 // Summation of counts for 'a', 'b', 'c', 'd' for the whole string
49 long result = 0;
50 for (int k = 0; k < 4; ++k) {
51 result += dp[0][n - 1][k];
52 }
53
54 return (int) (result % MOD); // Final result with mod operation
55 }
56}
571using ll = long long; // Define a type alias for long long integers.
2
3class Solution {
4public:
5 // Method to count all unique palindromic subsequences in the string.
6 int countPalindromicSubsequences(string s) {
7 const int mod = 1e9 + 7; // Define the modulo value for large numbers.
8 int n = s.size(); // Get the length of the input string.
9
10 // Initialize 3D dynamic programming array where dp[i][j][k] will contain the count
11 // of palindromic subsequences starting at i, ending at j,
12 // and beginning with the character 'a' + k.
13 vector<vector<vector<ll>>> dp(n, vector<vector<ll>>(n, vector<ll>(4, 0)));
14
15 // Base cases: single-character palindromes.
16 for (int i = 0; i < n; ++i) {
17 dp[i][i][s[i] - 'a'] = 1;
18 }
19
20 // Start populating the DP array for subsequences of length l.
21 for (int l = 2; l <= n; ++l) {
22 for (int i = 0; i + l <= n; ++i) {
23 int j = i + l - 1; // Calculate the end index of the current subsequence.
24 for (char c = 'a'; c <= 'd'; ++c) { // Iterate over each character from 'a' to 'd'.
25 int k = c - 'a'; // Convert char to corresponding index.
26 if (s[i] == c && s[j] == c) {
27 // If both ends match, all internal subsequences count twice (once including each end).
28 // Also, add 2 for the subsequences formed by the matching ends themselves.
29 dp[i][j][k] = 2 + accumulate(dp[i + 1][j - 1].begin(), dp[i + 1][j - 1].end(), 0ll) % mod;
30 } else if (s[i] == c) {
31 // If only the starting character matches c, inherit count from subsequences ending before j.
32 dp[i][j][k] = dp[i][j - 1][k];
33 } else if (s[j] == c) {
34 // If only the ending character matches c, inherit count from subsequences starting after i.
35 dp[i][j][k] = dp[i + 1][j][k];
36 } else {
37 // If neither end matches c, inherit count from internal subsequence.
38 dp[i][j][k] = dp[i + 1][j - 1][k];
39 }
40 }
41 }
42 }
43
44 // Collect the final answer from dp[0][n - 1], which contains all valid subsequences for the entire string.
45 ll ans = 0;
46 for (int k = 0; k < 4; k++) {
47 ans += dp[0][n - 1][k];
48 ans %= mod; // Ensure we take modulo after each addition.
49 }
50
51 return static_cast<int>(ans); // Cast the long long result back to int before returning.
52 }
53};
541type ll = number; // Define a type alias for long long integers (use 'number' in TypeScript).
2
3// Define the modulo value for large numbers.
4const MOD = 1e9 + 7;
5
6// Method to count all unique palindromic subsequences in the string.
7function countPalindromicSubsequences(s: string): number {
8 const n: number = s.length; // Get the length of the input string.
9
10 // Initialize 3D dynamic programming array where dp[i][j][k] will contain the count
11 // of palindromic subsequences starting at i, ending at j,
12 // and beginning with the character 'a' + k.
13 const dp: ll[][][] = Array.from({ length: n }, () =>
14 Array.from({ length: n }, () => Array(4).fill(0))
15 );
16
17 // Base cases: single-character palindromes.
18 for (let i = 0; i < n; ++i) {
19 dp[i][i][s.charCodeAt(i) - 'a'.charCodeAt(0)] = 1;
20 }
21
22 // Start populating the DP array for subsequences of length l.
23 for (let l = 2; l <= n; ++l) {
24 for (let i = 0; i + l <= n; ++i) {
25 let j = i + l - 1; // Calculate the end index of the current subsequence.
26 for (let c = 'a'.charCodeAt(0); c <= 'd'.charCodeAt(0); ++c) { // Iterate over each character from 'a' to 'd'.
27 let k = c - 'a'.charCodeAt(0); // Convert char code to corresponding index.
28 if (s[i] === String.fromCharCode(c) && s[j] === String.fromCharCode(c)) {
29 // If both ends match, all internal subsequences count twice (once including each end).
30 // Also, add 2 for the subsequences formed by the matching ends themselves.
31 dp[i][j][k] = (2 + dp[i + 1][j - 1].reduce((sum, val) => (sum + val) % MOD, 0)) % MOD;
32 } else if (s[i] === String.fromCharCode(c)) {
33 // If only the starting character matches c, inherit count from subsequences ending before j.
34 dp[i][j][k] = dp[i][j - 1][k];
35 } else if (s[j] === String.fromCharCode(c)) {
36 // If only the ending character matches c, inherit count from subsequences starting after i.
37 dp[i][j][k] = dp[i + 1][j][k];
38 } else {
39 // If neither end matches c, inherit count from internal subsequence.
40 dp[i][j][k] = dp[i + 1][j - 1][k];
41 }
42 }
43 }
44 }
45
46 // Collect the final answer from dp[0][n - 1], which contains all valid subsequences for the entire string.
47 let ans: ll = 0;
48 for (let k = 0; k < 4; k++) {
49 ans = (ans + dp[0][n - 1][k]) % MOD; // Ensure we take modulo after each addition.
50 }
51
52 return ans; // Return the result.
53}
54
55// Example usage:
56// console.log(countPalindromicSubsequences("abcd"));
57A heap is a ...?
Time and Space Complexity
Time Complexity
The time complexity of the provided code is primarily determined by the triple nested loops:
- The outermost loop runs for all subsequence lengths, from
2ton(the string length), resulting inO(n)iterations. - The middle loop runs for each starting index of the subsequence, which is also
O(n). - The innermost loop runs for each character
cin'abcd', leading to4iterations as there are4characters.
The core operation inside the innermost loop takes constant time except for the sum(dp[i + 1][j - 1]) operation, which is done in O(4) or constant time since it is a summation over an array with 4 elements.
Hence, the overall time complexity is O(n^2 * 4), which simplifies to O(n^2).
Space Complexity
The space complexity is determined by the size of the dp array, which is a three-dimensional array.
- The first dimension has
nelements wherenis the length of the string. - The second dimension also has
nelements representing the ending index of the subsequence. - The third dimension has
4elements corresponding to each charactercin'abcd'.
Thus, the space complexity is O(n^2 * 4). Since 4 is a constant and doesnât depend on n, it can be dropped in Big O notation, making the space complexity O(n^2).
Learn more about how to find time and space complexity quickly using problem constraints.
What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.