Question

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 1: Enumeration + Counting

The time complexity is $O(100 \times n)$, and the space complexity is $O(100 \times n)$. Where $n$ is the length of the string $s$.

class Solution:
  def countPalindromes(self, s: str) -> int:
    mod = 10**9 + 7
    n = len(s)
    pre = [[[0] * 10 for _ in range(10)] for _ in range(n + 2)]
    suf = [[[0] * 10 for _ in range(10)] for _ in range(n + 2)]
    t = list(map(int, s))
    c = [0] * 10
    for i, v in enumerate(t, 1):
      for j in range(10):
        for k in range(10):
          pre[i][j][k] = pre[i - 1][j][k]
      for j in range(10):
        pre[i][j][v] += c[j]
      c[v] += 1
    c = [0] * 10
    for i in range(n, 0, -1):
      v = t[i - 1]
      for j in range(10):
        for k in range(10):
          suf[i][j][k] = suf[i + 1][j][k]
      for j in range(10):
        suf[i][j][v] += c[j]
      c[v] += 1
    ans = 0
    for i in range(1, n + 1):
      for j in range(10):
        for k in range(10):
          ans += pre[i - 1][j][k] * suf[i + 1][j][k]
          ans %= mod
    return ans

class Solution {
  private static final int MOD = (int) 1e9 + 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;
  }
}

class Solution {
public:
  const int mod = 1e9 + 7;

  int countPalindromes(string s) {
    int n = s.size();
    int pre[n + 2][10][10];
    int suf[n + 2][10][10];
    memset(pre, 0, sizeof pre);
    memset(suf, 0, sizeof suf);
    int t[n];
    for (int i = 0; i < n; ++i) t[i] = s[i] - '0';
    int c[10] = {0};
    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]++;
    }
    memset(c, 0, sizeof c);
    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 += 1ll * pre[i - 1][j][k] * suf[i + 1][j][k];
          ans %= mod;
        }
      }
    }
    return ans;
  }
};

func countPalindromes(s string) int {
  n := len(s)
  pre := [10010][10][10]int{}
  suf := [10010][10][10]int{}
  t := make([]int, n)
  for i, c := range s {
    t[i] = int(c - '0')
  }
  c := [10]int{}
  for i := 1; i <= n; i++ {
    v := t[i-1]
    for j := 0; j < 10; j++ {
      for k := 0; k < 10; k++ {
        pre[i][j][k] = pre[i-1][j][k]
      }
    }
    for j := 0; j < 10; j++ {
      pre[i][j][v] += c[j]
    }
    c[v]++
  }
  c = [10]int{}
  for i := n; i > 0; i-- {
    v := t[i-1]
    for j := 0; j < 10; j++ {
      for k := 0; k < 10; k++ {
        suf[i][j][k] = suf[i+1][j][k]
      }
    }
    for j := 0; j < 10; j++ {
      suf[i][j][v] += c[j]
    }
    c[v]++
  }
  ans := 0
  const mod int = 1e9 + 7
  for i := 1; i <= n; i++ {
    for j := 0; j < 10; j++ {
      for k := 0; k < 10; k++ {
        ans += pre[i-1][j][k] * suf[i+1][j][k]
        ans %= mod
      }
    }
  }
  return ans
}