730. Count Different Palindromic Subsequences

HardStringDynamic Programming
Leetcode Link

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':

  1. If both ends of the substring i and j have the same character c, then the palindrome count for this character in dp[i][j][k] includes all the palindromes within s[i+1: j-1] plus 2 (for the subsequences made by the single character c and the one formed by cc).

  2. If only one end has the character c, then the palindrome count for this character in dp[i][j][k] is the same as in the substring s[i: j] or s[i+1: j+1], depending on which end has the character c.

  3. If neither end has the character c, then the count remains the same as in the substring s[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.

Solution Approach

The given Python solution implements a dynamic programming approach to solve the problem efficiently.

Breaking down the implementation we have:

  1. Initialization: The solution creates a 3-dimensional list (or array) dp which is initialized to hold all zeros. The dimensions of dp are [n][n][4], where n is the length of the string and 4 represents the four possible characters ('a', 'b', 'c', 'd').

  2. Base Case: For each character in the input string s, we set dp[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.

  3. Main Loop: The solution then iterates over all possible lengths of substrings l starting from 2 up to n inclusive. For each length, it loops over all possible starting indices i of the substring.

  4. State Transitions:

    • If the characters at both ends are the same and are the character c, the count dp[i][j][k] is calculated by adding 2 (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 by sum(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.

  5. Modular Arithmetic: As the answer can be very large, every time we calculate the sum, we take modulo 10^9 + 7 to keep the number within the integer range.

  6. Final Answer: After populating the dp array, the answer is the sum of dp[0][n - 1] (representing counts of different palindromic subsequences in the entire string from the first to the last character) modulo 10^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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example to illustrate the solution approach. Take the string s = "abca".

  1. Initialization: We create a 3D array dp of size [4][4][4], as the string length n is 4. This array will hold zeros initially.

  2. Base Case: We iterate over each character in s. For i = 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.

  1. Main Loop: We loop through all possible substring lengths l = 2...4. In this case, let's look at l = 2. We loop over all start indices i for this length.

    • For l = 2, substring ab (s[0:2]), we have i = 0:
      • The characters at s[0] and s[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.

  2. State Transitions: For l = 2, continue with the state transitions:

    • Look at substring bc (s[1:3]), where i = 1:
      • Characters at s[1] and s[2] are different, so dp[1][2][1] = dp[1][1][1] = 1, and dp[1][2][2] = dp[2][2][2] = 1.

  3. Continue Looping: Continue with l = 3 and then l = 4, updating the dp array 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] and dp[0][2][1] = dp[1][1][1].

  4. Final Answer: After populating the dp array for all substrings of all lengths, our answer would be the sum sum(dp[0][3]) modulo 10^9 + 7 for 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
41
1class 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}
57
1using 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};
54
1type 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"));
57

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 2 to n (the string length), resulting in O(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 c in 'abcd', leading to 4 iterations as there are 4 characters.

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 n elements where n is the length of the string.
  • The second dimension also has n elements representing the ending index of the subsequence.
  • The third dimension has 4 elements corresponding to each character c in '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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Recommended Readings

Dynamic Programming Introduction and Patterns

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

LeetCode Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we

Recursion Review

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

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More