Scale Engineer

Count Palindromic Subsequences

Hard
#2266Time: O(N^2 * D). The precomputation takes O(N * D). The main part consists of two nested loops for `j` and `l` (O(N^2)) and an inner loop for digits (O(D)). This is too slow for N = 10^4.Space: O(N * D), where N is the length of the string and D is the number of possible digits (10). This is for storing the prefix and suffix count arrays.3 companies
Patterns
Dynamic Programming
Data structures
String
Companies
Goldman SachsSalesforceCitadel

Prompt

Given a string of digits s, return the number of palindromic subsequences of s having length 5. Since the answer may be very large, return it modulo 109 + 7.

Note:

  • A string is palindromic if it reads the same forward and backward.
  • A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

 

Example 1:

Input: s = "103301"
Output: 2
Explanation: 
There are 6 possible subsequences of length 5: "10330","10331","10301","10301","13301","03301". 
Two of them (both equal to "10301") are palindromic.

Example 2:

Input: s = "0000000"
Output: 21
Explanation: All 21 subsequences are "00000", which is palindromic.

Example 3:

Input: s = "9999900000"
Output: 2
Explanation: The only two palindromic subsequences are "99999" and "00000".

 

Constraints:

  • 1 <= s.length <= 104
  • s consists of digits.

Approaches

3 approaches with complexity analysis and trade-offs.

A palindromic subsequence of length 5 has the structure xyzyx. A straightforward approach is to iterate through all possible indices for the inner pair yy. Let these indices be j and l. For each such pair where s[j] == s[l], we then count how many ways we can choose the outer pair xx and the middle element z.

The number of choices for z is simply the number of characters between j and l. The number of ways to choose xx can be found by using precomputed counts of each digit in the prefixes and suffixes of the string.

Algorithm

  • A palindromic subsequence of length 5 has the form xyzyx.
  • This approach focuses on finding the inner pair yy at indices j and l.
  • First, precompute two arrays:
    • prefix_counts[i][d]: the number of occurrences of digit d in the prefix s[0...i-1].
    • suffix_counts[i][d]: the number of occurrences of digit d in the suffix s[i+1...n-1].
    • Both can be computed in O(N*D) time, where N is the string length and D is the number of digits (10).
  • Initialize total_count = 0.
  • Iterate through all possible indices j for the first y from 1 to n-2.
  • In a nested loop, iterate through all possible indices l for the second y from j+1 to n-2.
  • If s.charAt(j) == s.charAt(l):
    • The number of choices for the middle element z is the number of characters between indices j and l, which is l - j - 1.
    • The number of ways to form the outer pair xx is calculated by summing over all digits d from 0 to 9: prefix_counts[j][d] * suffix_counts[l][d].
    • The contribution for this pair (j, l) is (l - j - 1) * (sum of pairs for x).
    • Add this contribution to total_count, taking modulo at each step.

Walkthrough

This approach iterates through all possible pairs of indices (j, l) to serve as the positions for the inner y characters of the palindrome xyzyx. For this to be valid, we must have j < l and s[j] == s[l].

For each valid (j, l) pair, we calculate the number of ways to complete the palindrome:

  1. Choosing z: The middle element z can be any character s[k] where j < k < l. The number of choices is l - j - 1.
  2. Choosing x: The outer x characters must be at indices i and m such that i < j and m > l, with s[i] == s[m]. To count these, we can sum over all possible digits d ('0' through '9'). For each d, the number of ways to choose the outer pair is (count of d before index j) * (count of d after index l).

To get these counts efficiently, we precompute prefix_counts[i][d] and suffix_counts[i][d]. The main part of the algorithm involves three nested loops: one for j, one for l, and one for the digit d to calculate the number of x pairs. The total count is the sum of contributions from all valid (j, l) pairs.

class Solution {    public int countPalindromicSubsequences(String s) {        int n = s.length();        int MOD = 1_000_000_007;        if (n < 5) {            return 0;        }         int[][] prefix_counts = new int[n][10];        int[][] suffix_counts = new int[n][10];        int[] s_digits = new int[n];        for(int i=0; i<n; i++) s_digits[i] = s.charAt(i) - '0';         // Precompute prefix counts        prefix_counts[0][s_digits[0]] = 1;        for (int i = 1; i < n; i++) {            for (int d = 0; d < 10; d++) {                prefix_counts[i][d] = prefix_counts[i - 1][d];            }            prefix_counts[i][s_digits[i]]++;        }         // Precompute suffix counts        suffix_counts[n - 1][s_digits[n - 1]] = 1;        for (int i = n - 2; i >= 0; i--) {            for (int d = 0; d < 10; d++) {                suffix_counts[i][d] = suffix_counts[i + 1][d];            }            suffix_counts[i][s_digits[i]]++;        }         long totalCount = 0;        for (int j = 1; j < n - 1; j++) {            for (int l = j + 1; l < n - 1; l++) {                if (s_digits[j] == s_digits[l]) {                    long num_z = l - j - 1;                    if (num_z <= 0) continue;                     long num_x_pairs = 0;                    for (int d = 0; d < 10; d++) {                        long count_before_j = (j > 0) ? prefix_counts[j - 1][d] : 0;                        long count_after_l = (l < n - 1) ? suffix_counts[l + 1][d] : 0;                        num_x_pairs = (num_x_pairs + count_before_j * count_after_l) % MOD;                    }                    totalCount = (totalCount + num_z * num_x_pairs) % MOD;                }            }        }         return (int) totalCount;    }}

Complexity

Time

O(N^2 * D). The precomputation takes O(N * D). The main part consists of two nested loops for `j` and `l` (O(N^2)) and an inner loop for digits (O(D)). This is too slow for N = 10^4.

Space

O(N * D), where N is the length of the string and D is the number of possible digits (10). This is for storing the prefix and suffix count arrays.

Trade-offs

Pros

  • Conceptually simple and a direct translation of the counting problem.

  • Easier to implement than more optimized solutions.

Cons

  • The time complexity is too high for the given constraints, leading to a Time Limit Exceeded (TLE) error.

Solutions

class Solution {private  static final int MOD = (int)1 e9 + 7;public  int countPalindromes(String s) {    int n = s.length();    int[][][] pre = new int[n + 2][10][10];    int[][][] suf = new int[n + 2][10][10];    int[] t = new int[n];    for (int i = 0; i < n; ++i) {      t[i] = s.charAt(i) - '0';    }    int[] c = new int[10];    for (int i = 1; i <= n; ++i) {      int v = t[i - 1];      for (int j = 0; j < 10; ++j) {        for (int k = 0; k < 10; ++k) {          pre[i][j][k] = pre[i - 1][j][k];        }      }      for (int j = 0; j < 10; ++j) {        pre[i][j][v] += c[j];      }      c[v]++;    }    c = new int[10];    for (int i = n; i > 0; --i) {      int v = t[i - 1];      for (int j = 0; j < 10; ++j) {        for (int k = 0; k < 10; ++k) {          suf[i][j][k] = suf[i + 1][j][k];        }      }      for (int j = 0; j < 10; ++j) {        suf[i][j][v] += c[j];      }      c[v]++;    }    long ans = 0;    for (int i = 1; i <= n; ++i) {      for (int j = 0; j < 10; ++j) {        for (int k = 0; k < 10; ++k) {          ans += (long)pre[i - 1][j][k] * suf[i + 1][j][k];          ans %= MOD;        }      }    }    return (int)ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem