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:
pre
: For each prefix of the string ending at positioni
, and for every pair of digitsj
andk
, the solution records the number of times the subsequence ofj
followed byk
happens before positioni
.suf
: Similarly, for each suffix of the string starting at positioni
, and for every pair of digitsj
andk
, it records the number of times the subsequence ofj
followed byk
happens after positioni
.
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 modulo10^9 + 7
to prevent potential integer overflow issues caused by very large outputs.n
: The length of the input strings
.pre
andsuf
: Three-dimensional arrays (lists of lists of lists) used to store the count of subsequences wherepre[i][j][k]
represents the number of subsequences of the formj*
ending before positioni
andsuf[i][j][k]
represents the same but starting after positioni
fork*
.c
: A list used to keep track of the count of each digit encountered while iterating over the string.t
: The strings
, converted into a list of integers for easier manipulation.ans
: The variable used to store the final answer.
The implementation follows these steps:
-
Initialize
pre
andsuf
with 0s and setc
to a list of 10 zeros (one for each possible digit). -
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 indexi - 1
.b. Increment the count of the current digit in
c
. -
Reset
c
to a list of zeros. -
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 indexi
.b. Increment the count of the current digit in
c
. -
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
), incrementans
by the product of the counts inpre[i - 1][j][k]
andsuf[i + 1][j][k]
, each time taking the result modulomod
. -
Return the calculated
ans
value, which is the count of palindromic subsequences of length 5 modulo10^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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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.
-
We initialize
pre
andsuf
with zeros and setc
to a list of 10 zeros. Our strings
is converted into a list of integers,t = [1, 1, 3, 4, 5]
. -
Now we iterate over
t
from left to right. After the iteration, we will end up with thepre
array having counts of how many times pairs of digits (for instance1*
) appear before indexi
.- For
i = 0
(t[0] = 1
), there are no digits before it, sopre
array doesn't change. - For
i = 1
(t[1] = 1
), we updatepre[2][1][*]
(for all*
) to count pairs that end with1
. - For
i = 2
(t[2] = 3
), we updatepre[3][3][1]
since we have encountered two '1's before. - For
i = 3
andi = 4
, we similarly update counts for pairs ending with '4' and '5'.
- For
-
We reset
c
to zeros for the backwards pass, and iterate throught
from right to left. This is similar to the previous step but now we're filling thesuf
array, which holds the counts of pairs starting with each digit after indexi
. -
Next, we loop through each possible central digit of a palindrome.
a. For
i = 2
which is '3', we find nopre[1][1][*]
orsuf[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' andi = 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
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.
-
The first loop runs through the string
s
of lengthn
and, for each character, updates thepre
matrix. Since thepre
matrix is a 3D array with dimensionsn x 10 x 10
, and for each of then
characters it does constant work (iterating over a 10x10 matrix), this loop runs inO(10 * 10 * n)
time, which simplifies toO(n)
because the10 * 10
is a constant. -
The second loop is similar to the first one but iterates backward, updating the
suf
matrix. The time complexity is alsoO(n)
for the same reasons as the first loop. -
The third loop iterates over the
n
characters, and for each character, it does work proportional to10 * 10
(iterating over every possible pair of digits). Therefore, the complexity for this loop isO(10 * 10 * n)
which again simplifies toO(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.
-
The
pre
andsuf
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 is2 * (n + 2) * 10 * 10
. This simplifies toO(n)
, since10 * 10
is constant andn
is the dominant term. -
The
c
array has a constant size of10
, which is independent ofn
and thusO(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.
Which algorithm should you use to find a node that is close to the root of the tree?
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
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 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 Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.