2484. Count Palindromic Subsequences

Description

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.

 

Solutions

Solution: Dynamic Programming

• Time complexity: O(10*10*5*n -> n)
• Space complexity: O(1)

 

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
const countPalindromes = function (s) {
  const SUBSEQ_SIZE = 5;
  const MODULO = 10 ** 9 + 7;
  let result = 0;

  for (let a = 0; a < 10; a++) {
    for (let b = 0; b < 10; b++) {
      const palindromic = [`${a}`, `${b}`, '#', `${b}`, `${a}`];
      const dp = new Array(SUBSEQ_SIZE + 1).fill(0);

      dp[SUBSEQ_SIZE] = 1;

      for (const char of s) {
        for (let index = 0; index < SUBSEQ_SIZE; index++) {
          const current = palindromic[index];

          if (current === '#' || current === char) {
            dp[index] = (dp[index] + dp[index + 1]) % MODULO;
          }
        }
      }

      result = (result + dp[0]) % MODULO;
    }
  }

  return result;
};