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.

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.

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

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.