730. Count Different Palindromic Subsequences

Description

Given a string s, return the number of different non-empty palindromic subsequences in s. Since the answer may be very large, return it modulo 109 + 7.

A subsequence of a string is obtained by deleting zero or more characters from the string.

A sequence is palindromic if it is equal to the sequence reversed.

Two sequences a1, a2, ... and b1, b2, ... are different if there is some i for which ai != bi.

 

Example 1:

Input: s = "bccb"
Output: 6
Explanation: The 6 different non-empty palindromic subsequences are 'b', 'c', 'bb', 'cc', 'bcb', 'bccb'.
Note that 'bcb' is counted only once, even though it occurs twice.

Example 2:

Input: s = "abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba"
Output: 104860361
Explanation: There are 3104860382 different non-empty palindromic subsequences, which is 104860361 modulo 109 + 7.

 

Constraints:

• 1 <= s.length <= 1000
• s[i] is either 'a', 'b', 'c', or 'd'.

 

Solutions

Solution: Dynamic Programming

• Time complexity: O(n²logn)
• Space complexity: O(n²)

 

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
const countPalindromicSubsequences = function (s) {
  const MODULO = 10 ** 9 + 7;
  const BASE_CODE = 'a'.charCodeAt(0);
  const CHARS_COUNT = 4;
  const n = s.length;
  const chars = Array.from({length: CHARS_COUNT})
    .fill('')
    .map(_ => []);
  const memo = new Array(n)
    .fill('')
    .map(_ => new Array(n).fill(0));

  for (let index = 0; index < n; index++) {
    const code = s[index].charCodeAt(0) - BASE_CODE;

    chars[code].push(index);
  }

  const binarySearch = (arr, target) => {
    let left = 0;
    let right = arr.length;

    while (left < right) {
      const mid = Math.floor((left + right) / 2);

      arr[mid] >= target ? (right = mid) : (left = mid + 1);
    }
    return left;
  };

  const countPalindromic = (left, right) => {
    if (left > right) return 0;
    if (memo[left][right]) return memo[left][right];

    let result = 0;

    for (let index = 0; index < CHARS_COUNT; index++) {
      const charIndices = chars[index];

      if (!charIndices.length) continue;
      const charLeft = binarySearch(charIndices, left);

      if (charLeft === charIndices.length) continue;
      if (charIndices[charLeft] > right) continue;
      const charRight = binarySearch(charIndices, right + 1) - 1;

      result += charLeft === charRight ? 1 : 2;
      result += countPalindromic(charIndices[charLeft] + 1, charIndices[charRight] - 1);
      result %= MODULO;
    }
    return (memo[left][right] = result);
  };

  return countPalindromic(0, n - 1);
};