2484. Count Palindromic Subsequences


Problem Description

The problem asks for a count of palindromic subsequences of length 5 in a given string s comprised only of digits. To clarify, a palindromic subsequence is a sequence of characters that reads the same forwards and backwards, and a subsequence is derived by removing zero or more characters from a string without altering the order of the remaining characters. Because the expected number of palindromic subsequences could be very large, the output should be given as the remainder when divided by (10^9 + 7).

For example, if s = "12345", there are no palindromic subsequences of length 5, so the result would be 0. If s = "11111", then the string itself is a palindromic subsequence (in fact, it's the only one since all characters are the same), so the result would be 1.

Intuition

To understand the solution, it's important to recognize that a palindromic subsequence of length 5 has a specific format: it starts and ends with the same digit, and the middle digit is also the same as these two digits or different.

The sequences will look like this: AABBX, AAXAA, or other permutations where A and B are digits (with A equal B or A different from B) and X can be any digit. Therefore, the focus is on counting the possibilities of finding such arrangements within the given string.

To count such sequences efficiently, dynamic programming concepts are employed. The solution iterates through the string, progressively calculating two kinds of information:

  1. pre: For each prefix of the string ending at position i, and for every pair of digits j and k, the solution records the number of times the subsequence of j followed by k happens before position i.
  2. suf: Similarly, for each suffix of the string starting at position i, and for every pair of digits j and k, it records the number of times the subsequence of j followed by k happens after position i.

Armed with this precomputed information (pre and suf arrays), for every central digit at index i in the string, the solution multiplies the prefix counts by the suffix counts. It does this for all combinations of j and k around i. By multiplying the counts, it's effectively counting all possible unique 5-length palindromic subsequences that could be formed if i was the middle digit.

Overall, this approach avoids a brute force check of all possible subsequences by intelligently counting combination possibilities around each viable middle position, greatly reducing runtime complexity.

Learn more about Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

How many times is a tree node visited in a depth first search?

Solution Approach

The solution uses dynamic programming to build up information about possible palindromic sequences as it iterates over the input string. The significant variables used in this solution are:

  • mod: A constant value used for taking the result modulo 10^9 + 7 to prevent potential integer overflow issues caused by very large outputs.
  • n: The length of the input string s.
  • pre and suf: Three-dimensional arrays (lists of lists of lists) used to store the count of subsequences where pre[i][j][k] represents the number of subsequences of the form j* ending before position i and suf[i][j][k] represents the same but starting after position i for k*.
  • c: A list used to keep track of the count of each digit encountered while iterating over the string.
  • t: The string s, converted into a list of integers for easier manipulation.
  • ans: The variable used to store the final answer.

The implementation follows these steps:

  1. Initialize pre and suf with 0s and set c to a list of 10 zeros (one for each possible digit).

  2. Iterate through the string s from left to right (forward direction):

    a. Update the pre array using the current counts of all digit pairs ending with the current digit at index i - 1.

    b. Increment the count of the current digit in c.

  3. Reset c to a list of zeros.

  4. Iterate through the string s from right to left (backward direction):

    a. Update the suf array using the current counts of all digit pairs starting with the current digit at index i.

    b. Increment the count of the current digit in c.

  5. Loop through each position i in the string (considering it as a central digit of a possible palindrome) and for each possible pair of digits (j, k), increment ans by the product of the counts in pre[i - 1][j][k] and suf[i + 1][j][k], each time taking the result modulo mod.

  6. Return the calculated ans value, which is the count of palindromic subsequences of length 5 modulo 10^9 + 7.

This approach effectively short-circuits the combinatorial explosion typical of substring problems by only counting unique subsequences that meet the palindrome criteria, made possible by leveraging dynamic programming to remember useful counts.

In terms of algorithms and patterns:

  • Dynamic Programming is used to avoid recalculations and to store intermediate results for subproblems.
  • The iteration pattern cleverly combines forward and backwards passes to pre-compute values needed for the final calculation.

The choice of data structures (2D and 3D arrays) is aimed towards fast access and update times, enabling the innermost loop to efficiently compute combinations for the final result.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following array represent a max heap?

Example Walkthrough

Let's illustrate the solution approach with a small example using the string s = "11345". We want to count the number of palindromic subsequences of length 5.

  1. We initialize pre and suf with zeros and set c to a list of 10 zeros. Our string s is converted into a list of integers, t = [1, 1, 3, 4, 5].

  2. Now we iterate over t from left to right. After the iteration, we will end up with the pre array having counts of how many times pairs of digits (for instance 1*) appear before index i.

    • For i = 0 (t[0] = 1), there are no digits before it, so pre array doesn't change.
    • For i = 1 (t[1] = 1), we update pre[2][1][*] (for all *) to count pairs that end with 1.
    • For i = 2 (t[2] = 3), we update pre[3][3][1] since we have encountered two '1's before.
    • For i = 3 and i = 4, we similarly update counts for pairs ending with '4' and '5'.
  3. We reset c to zeros for the backwards pass, and iterate through t from right to left. This is similar to the previous step but now we're filling the suf array, which holds the counts of pairs starting with each digit after index i.

  4. Next, we loop through each possible central digit of a palindrome.

    a. For i = 2 which is '3', we find no pre[1][1][*] or suf[3][1][*] combinations since the pairs we need for a palindrome must start and end with the same digit. So in this case, there's no palindrome centered at '3'.

    b. For i = 3 which is '4' and i = 4 which is '5', the situation is the same.

The final result is ans = 0, as there are no palindromic subsequences of length 5 in this string.

This walk-through example demonstrates how the algorithm calculates all potential palindromic subsequences centered around each character in the string without exhaustively checking each subsequence. The pre-computation of pre and suf arrays simplifies the overall process by providing necessary counts of digit pairs before and after each index, ready to be used in the final computation.

Solution Implementation

1class Solution:
2    def count_palindromes(self, s: str) -> int:
3        # Define the modulus for taking modulo operations
4        mod = 10**9 + 7
5      
6        # Calculate the length of the string
7        n = len(s)
8      
9        # Initialize prefix and suffix arrays with extra 2 rows for padding
10        prefix = [[[0] * 10 for _ in range(10)] for _ in range(n + 2)]
11        suffix = [[[0] * 10 for _ in range(10)] for _ in range(n + 2)]
12      
13        # Convert string to a list of integers for easier manipulation
14        digits = list(map(int, s))
15      
16        # Create and initialize the count array for digits
17        digit_count = [0] * 10
18      
19        # Calculate prefix tables
20        for i, value in enumerate(digits, 1):
21            for j in range(10):
22                for k in range(10):
23                    prefix[i][j][k] = prefix[i - 1][j][k]
24            for j in range(10):
25                prefix[i][j][value] += digit_count[j]
26            digit_count[value] += 1
27      
28        # Reset the count array for the suffix calculations
29        digit_count = [0] * 10
30      
31        # Calculate suffix tables in reverse
32        for i in range(n, 0, -1):
33            value = digits[i - 1]
34            for j in range(10):
35                for k in range(10):
36                    suffix[i][j][k] = suffix[i + 1][j][k]
37            for j in range(10):
38                suffix[i][j][value] += digit_count[j]
39            digit_count[value] += 1
40      
41        # Initialize variable for storing the final answer
42        answer = 0
43      
44        # Calculate the number of palindromes using prefix and suffix tables
45        for i in range(1, n + 1):
46            for j in range(10):
47                for k in range(10):
48                    answer += prefix[i - 1][j][k] * suffix[i + 1][j][k]
49                    answer %= mod
50      
51        # Return the final count of palindromes modulo mod
52        return answer
53
1class Solution {
2    private static final int MODULO = (int) 1e9 + 7; // Define a constant for the modulus value
3
4    public int countPalindromes(String s) {
5        int length = s.length(); // Get the length of the string
6        int[][][] prefixCounts = new int[length + 2][10][10]; // Prefix count array
7        int[][][] suffixCounts = new int[length + 2][10][10]; // Suffix count array
8        int[] digits = new int[length]; // Array to store the numerical value of each character in the string
9      
10        // Populate the digits array with the numerical values of the string characters
11        for (int i = 0; i < length; ++i) {
12            digits[i] = s.charAt(i) - '0';
13        }
14      
15        int[] count = new int[10]; // Array to count occurrences of each digit
16        // Calculate prefix counts
17        for (int i = 1; i <= length; ++i) {
18            int value = digits[i - 1];
19            for (int j = 0; j < 10; ++j) {
20                for (int k = 0; k < 10; ++k) {
21                    prefixCounts[i][j][k] = prefixCounts[i - 1][j][k];
22                }
23            }
24            for (int j = 0; j < 10; ++j) {
25                prefixCounts[i][j][value] += count[j];
26            }
27            count[value]++;
28        }
29      
30        count = new int[10]; // Reset the count array for suffix counts
31        // Calculate suffix counts
32        for (int i = length; i > 0; --i) {
33            int value = digits[i - 1];
34            for (int j = 0; j < 10; ++j) {
35                for (int k = 0; k < 10; ++k) {
36                    suffixCounts[i][j][k] = suffixCounts[i + 1][j][k];
37                }
38            }
39            for (int j = 0; j < 10; ++j) {
40                suffixCounts[i][j][value] += count[j];
41            }
42            count[value]++;
43        }
44      
45        // Calculate the total count of palindrome pairs
46        long answer = 0;
47        for (int i = 1; i <= length; ++i) {
48            for (int j = 0; j < 10; ++j) {
49                for (int k = 0; k < 10; ++k) {
50                    answer += (long) prefixCounts[i - 1][j][k] * suffixCounts[i + 1][j][k];
51                    answer %= MODULO; // Ensure the answer stays within the modulo
52                }
53            }
54        }
55        return (int) answer; // Return the calculated answer
56    }
57}
58
1#include <cstring>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7    const int MOD = 1e9 + 7;
8
9    int countPalindromes(std::string s) {
10        int n = s.size();
11        // Define prefix and suffix arrays to hold counts of characters
12        int prefix[n + 2][10][10] = {};
13        int suffix[n + 2][10][10] = {};
14        std::vector<int> digits(n);
15      
16        // Convert input string to vector of digits
17        for (int i = 0; i < n; ++i) {
18            digits[i] = s[i] - '0';
19        }
20
21        std::vector<int> count(10, 0);
22      
23        // Calculate prefix counts
24        for (int i = 1; i <= n; ++i) {
25            int digit = digits[i - 1];
26            for (int j = 0; j < 10; ++j) {
27                for (int k = 0; k < 10; ++k) {
28                    prefix[i][j][k] = prefix[i - 1][j][k];
29                }
30            }
31            for (int j = 0; j < 10; ++j) {
32                prefix[i][j][digit] += count[j];
33            }
34            count[digit]++;
35        }
36
37        count.assign(10, 0); // Reset the count vector for suffix calculation
38      
39        // Calculate suffix counts
40        for (int i = n; i > 0; --i) {
41            int digit = digits[i - 1];
42            for (int j = 0; j < 10; ++j) {
43                for (int k = 0; k < 10; ++k) {
44                    suffix[i][j][k] = suffix[i + 1][j][k];
45                }
46            }
47            for (int j = 0; j < 10; ++j) {
48                suffix[i][j][digit] += count[j];
49            }
50            count[digit]++;
51        }
52
53        // Calculate the answer by considering all palindromes
54        long long ans = 0;
55        for (int i = 1; i <= n; ++i) {
56            for (int j = 0; j < 10; ++j) {
57                for (int k = 0; k < 10; ++k) {
58                    ans += static_cast<long long>(prefix[i - 1][j][k]) * suffix[i + 1][j][k];
59                    ans %= MOD;
60                }
61            }
62        }
63
64        // Return the final count
65        return static_cast<int>(ans);
66    }
67};
68
1// Constant for modulo operation
2const MOD = 1e9 + 7;
3
4// Function to count the number of palindromes
5function countPalindromes(s: string): number {
6    const n = s.length;
7    // Define prefix and suffix arrays to hold counts of characters
8    const prefix: number[][][] = Array.from({ length: n + 2 }, () => Array.from({ length: 10 }, () => Array(10).fill(0)));
9    const suffix: number[][][] = Array.from({ length: n + 2 }, () => Array.from({ length: 10 }, () => Array(10).fill(0)));
10    const digits: number[] = Array.from(s, (ch) => parseInt(ch));
11
12    const count: number[] = Array(10).fill(0);
13
14    // Calculate prefix counts
15    for (let i = 1; i <= n; ++i) {
16        const digit = digits[i - 1];
17        for (let j = 0; j < 10; ++j) {
18            for (let k = 0; k < 10; ++k) {
19                prefix[i][j][k] = prefix[i - 1][j][k];
20            }
21        }
22        for (let j = 0; j < 10; ++j) {
23            prefix[i][j][digit] += count[j];
24        }
25        count[digit]++;
26    }
27
28    // Reset the count array for suffix calculation
29    count.fill(0);
30
31    // Calculate suffix counts
32    for (let i = n; i > 0; --i) {
33        const digit = digits[i - 1];
34        for (let j = 0; j < 10; ++j) {
35            for (let k = 0; k < 10; ++k) {
36                suffix[i][j][k] = suffix[i + 1][j][k];
37            }
38        }
39        for (let j = 0; j < 10; ++j) {
40            suffix[i][j][digit] += count[j];
41        }
42        count[digit]++;
43    }
44
45    // Calculate the final count by considering all palindromes
46    let answer: number = 0;
47    for (let i = 1; i <= n; ++i) {
48        for (let j = 0; j < 10; ++j) {
49            for (let k = 0; k < 10; ++k) {
50                answer += prefix[i - 1][j][k] * suffix[i + 1][j][k];
51                answer %= MOD;
52            }
53        }
54    }
55
56    // Return the final count
57    return answer;
58}
59
Not Sure What to Study? Take the 2-min Quiz:

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Time and Space Complexity

Time Complexity

The given code consists of three primary loops: the first and the second for building pre and suf matrices, and the third to compute the final answer ans based on the pre and suf values.

  1. The first loop runs through the string s of length n and, for each character, updates the pre matrix. Since the pre matrix is a 3D array with dimensions n x 10 x 10, and for each of the n characters it does constant work (iterating over a 10x10 matrix), this loop runs in O(10 * 10 * n) time, which simplifies to O(n) because the 10 * 10 is a constant.

  2. The second loop is similar to the first one but iterates backward, updating the suf matrix. The time complexity is also O(n) for the same reasons as the first loop.

  3. The third loop iterates over the n characters, and for each character, it does work proportional to 10 * 10 (iterating over every possible pair of digits). Therefore, the complexity for this loop is O(10 * 10 * n) which again simplifies to O(n).

Since these loops run sequentially and not nested within each other, we add the complexities, which results in O(n) + O(n) + O(n) or simply O(n) time complexity overall, as the constant factors and the additional O(n) terms don't change the linear nature of the time complexity with respect to the length of the string.

Space Complexity

The space complexity is determined by the auxiliary space used by the program, which primarily comes from the pre and suf matrices and the c array.

  1. The pre and suf matrices each have a size of (n + 2) x 10 x 10. Since we have two such matrices, the total space taken up by them is 2 * (n + 2) * 10 * 10. This simplifies to O(n), since 10 * 10 is constant and n is the dominant term.

  2. The c array has a constant size of 10, which is independent of n and thus O(1) space complexity.

Adding the space complexities of pre, suf, and c gives us O(n) + O(n) + O(1), which simplifies to O(n) space complexity, as the constant space for c does not impact the overall space complexity which is dominated by the size of n.

Hence, the space complexity of the code is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

A heap is a ...?


Recommended Readings


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.


TA 👨‍🏫