Question

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 1

class Solution:
  def countPalindromicSubsequences(self, s: str) -> int:
    mod = 10**9 + 7
    n = len(s)
    dp = [[[0] * 4 for _ in range(n)] for _ in range(n)]
    for i, c in enumerate(s):
      dp[i][i][ord(c) - ord('a')] = 1
    for l in range(2, n + 1):
      for i in range(n - l + 1):
        j = i + l - 1
        for c in 'abcd':
          k = ord(c) - ord('a')
          if s[i] == s[j] == c:
            dp[i][j][k] = 2 + sum(dp[i + 1][j - 1])
          elif s[i] == c:
            dp[i][j][k] = dp[i][j - 1][k]
          elif s[j] == c:
            dp[i][j][k] = dp[i + 1][j][k]
          else:
            dp[i][j][k] = dp[i + 1][j - 1][k]
    return sum(dp[0][-1]) % mod

class Solution {
  private final int MOD = (int) 1e9 + 7;

  public int countPalindromicSubsequences(String s) {
    int n = s.length();
    long[][][] dp = new long[n][n][4];
    for (int i = 0; i < n; ++i) {
      dp[i][i][s.charAt(i) - 'a'] = 1;
    }
    for (int l = 2; l <= n; ++l) {
      for (int i = 0; i + l <= n; ++i) {
        int j = i + l - 1;
        for (char c = 'a'; c <= 'd'; ++c) {
          int k = c - 'a';
          if (s.charAt(i) == c && s.charAt(j) == c) {
            dp[i][j][k] = 2 + dp[i + 1][j - 1][0] + dp[i + 1][j - 1][1]
              + dp[i + 1][j - 1][2] + dp[i + 1][j - 1][3];
            dp[i][j][k] %= MOD;
          } else if (s.charAt(i) == c) {
            dp[i][j][k] = dp[i][j - 1][k];
          } else if (s.charAt(j) == c) {
            dp[i][j][k] = dp[i + 1][j][k];
          } else {
            dp[i][j][k] = dp[i + 1][j - 1][k];
          }
        }
      }
    }
    long ans = 0;
    for (int k = 0; k < 4; ++k) {
      ans += dp[0][n - 1][k];
    }
    return (int) (ans % MOD);
  }
}

using ll = long long;

class Solution {
public:
  int countPalindromicSubsequences(string s) {
    int mod = 1e9 + 7;
    int n = s.size();
    vector<vector<vector<ll>>> dp(n, vector<vector<ll>>(n, vector<ll>(4)));
    for (int i = 0; i < n; ++i) dp[i][i][s[i] - 'a'] = 1;
    for (int l = 2; l <= n; ++l) {
      for (int i = 0; i + l <= n; ++i) {
        int j = i + l - 1;
        for (char c = 'a'; c <= 'd'; ++c) {
          int k = c - 'a';
          if (s[i] == c && s[j] == c)
            dp[i][j][k] = 2 + accumulate(dp[i + 1][j - 1].begin(), dp[i + 1][j - 1].end(), 0ll) % mod;
          else if (s[i] == c)
            dp[i][j][k] = dp[i][j - 1][k];
          else if (s[j] == c)
            dp[i][j][k] = dp[i + 1][j][k];
          else
            dp[i][j][k] = dp[i + 1][j - 1][k];
        }
      }
    }
    ll ans = accumulate(dp[0][n - 1].begin(), dp[0][n - 1].end(), 0ll);
    return (int) (ans % mod);
  }
};

func countPalindromicSubsequences(s string) int {
  mod := int(1e9) + 7
  n := len(s)
  dp := make([][][]int, n)
  for i := range dp {
    dp[i] = make([][]int, n)
    for j := range dp[i] {
      dp[i][j] = make([]int, 4)
    }
  }
  for i, c := range s {
    dp[i][i][c-'a'] = 1
  }
  for l := 2; l <= n; l++ {
    for i := 0; i+l <= n; i++ {
      j := i + l - 1
      for _, c := range [4]byte{'a', 'b', 'c', 'd'} {
        k := int(c - 'a')
        if s[i] == c && s[j] == c {
          dp[i][j][k] = 2 + (dp[i+1][j-1][0]+dp[i+1][j-1][1]+dp[i+1][j-1][2]+dp[i+1][j-1][3])%mod
        } else if s[i] == c {
          dp[i][j][k] = dp[i][j-1][k]
        } else if s[j] == c {
          dp[i][j][k] = dp[i+1][j][k]
        } else {
          dp[i][j][k] = dp[i+1][j-1][k]
        }
      }
    }
  }
  ans := 0
  for _, v := range dp[0][n-1] {
    ans += v
  }
  return ans % mod
}