Skip to content

730. Count Different Palindromic Subsequences 👍

  • Time: $O(n^2)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
 public:
  int countPalindromicSubsequences(string s) {
    constexpr int kMod = 1'000'000'007;
    const int n = s.length();
    // dp[i][j] := the number of different non-empty palindromic subsequences in
    // s[i..j]
    vector<vector<long>> dp(n, vector<long>(n));

    for (int i = 0; i < n; ++i)
      dp[i][i] = 1;

    for (int d = 1; d < n; ++d)
      for (int i = 0; i + d < n; ++i) {
        const int j = i + d;
        if (s[i] == s[j]) {
          int lo = i + 1;
          int hi = j - 1;
          while (lo <= hi && s[lo] != s[i])
            ++lo;
          while (lo <= hi && s[hi] != s[i])
            --hi;
          if (lo > hi)
            dp[i][j] = dp[i + 1][j - 1] * 2 + 2;
          else if (lo == hi)
            dp[i][j] = dp[i + 1][j - 1] * 2 + 1;
          else
            dp[i][j] = dp[i + 1][j - 1] * 2 - dp[lo + 1][hi - 1];
        } else {
          dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1];
        }
        dp[i][j] = (dp[i][j] + kMod) % kMod;
      }

    return dp[0][n - 1];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
  public int countPalindromicSubsequences(String s) {
    final int kMod = 1_000_000_007;
    final int n = s.length();
    // dp[i][j] := the number of different non-empty palindromic subsequences in
    // s[i..j]
    int[][] dp = new int[n][n];

    for (int i = 0; i < n; ++i)
      dp[i][i] = 1;

    for (int d = 1; d < n; ++d)
      for (int i = 0; i + d < n; ++i) {
        final int j = i + d;
        if (s.charAt(i) == s.charAt(j)) {
          int lo = i + 1;
          int hi = j - 1;
          while (lo <= hi && s.charAt(lo) != s.charAt(i))
            ++lo;
          while (lo <= hi && s.charAt(hi) != s.charAt(i))
            --hi;
          if (lo > hi)
            dp[i][j] = dp[i + 1][j - 1] * 2 + 2;
          else if (lo == hi)
            dp[i][j] = dp[i + 1][j - 1] * 2 + 1;
          else
            dp[i][j] = dp[i + 1][j - 1] * 2 - dp[lo + 1][hi - 1];
        } else {
          dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1];
        }
        dp[i][j] = (int) ((dp[i][j] + kMod) % kMod);
      }

    return dp[0][n - 1];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
  def countPalindromicSubsequences(self, s: str) -> int:
    kMod = 1_000_000_007
    n = len(s)
    # dp[i][j] := the number of different non-empty palindromic subsequences in
    # s[i..j]
    dp = [[0] * n for _ in range(n)]

    for i in range(n):
      dp[i][i] = 1

    for d in range(1, n):
      for i in range(n - d):
        j = i + d
        if s[i] == s[j]:
          lo = i + 1
          hi = j - 1
          while lo <= hi and s[lo] != s[i]:
            lo += 1
          while lo <= hi and s[hi] != s[i]:
            hi -= 1
          if lo > hi:
            dp[i][j] = dp[i + 1][j - 1] * 2 + 2
          elif lo == hi:
            dp[i][j] = dp[i + 1][j - 1] * 2 + 1
          else:
            dp[i][j] = dp[i + 1][j - 1] * 2 - dp[lo + 1][hi - 1]
        else:
          dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1]
        dp[i][j] = (dp[i][j] + kMod) % kMod

    return dp[0][n - 1]