Skip to content

2484. Count Palindromic Subsequences 👍

  • Time: $O(n)$
  • Space: $O(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
class Solution {
 public:
  int countPalindromes(string s) {
    constexpr int kMod = 1'000'000'007;
    constexpr int kPatternSize = 5;
    long ans = 0;

    for (char a = '0'; a <= '9'; ++a)
      for (char b = '0'; b <= '9'; ++b) {
        const vector<char> pattern{a, b, '.', b, a};
        // dp[i] := the number of subsequences of pattern[i..n) in s, where
        // pattern[2] can be any character
        vector<long> dp(kPatternSize + 1);
        dp.back() = 1;
        for (const char c : s)
          for (int i = 0; i < kPatternSize; ++i)
            if (pattern[i] == '.' || pattern[i] == c)
              dp[i] += dp[i + 1];
        ans += dp[0];
        ans %= kMod;
      }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
  public int countPalindromes(String s) {
    final int kMod = 1_000_000_007;
    final int kPatternSize = 5;
    long ans = 0;

    for (char a = '0'; a <= '9'; ++a)
      for (char b = '0'; b <= '9'; ++b) {
        char[] pattern = {a, b, '.', b, a};
        // dp[i] := the number of subsequences of pattern[i..n) in s, where
        // pattern[2] can be any character
        long[] dp = new long[kPatternSize + 1];
        dp[kPatternSize] = 1;
        for (final char c : s.toCharArray())
          for (int i = 0; i < kPatternSize; ++i)
            if (pattern[i] == '.' || pattern[i] == c)
              dp[i] += dp[i + 1];
        ans += dp[0];
        ans %= kMod;
      }

    return (int) ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def countPalindromes(self, s: str) -> int:
    kMod = 1_000_000_007
    ans = 0

    for a in range(10):
      for b in range(10):
        pattern = f'{a}{b}.{b}{a}'
        # dp[i] := the number of subsequences of pattern[i..n) in s, where
        # pattern[2] can be any character
        dp = [0] * 5 + [1]
        for c in s:
          for i, p in enumerate(pattern):
            if p == '.' or p == c:
              dp[i] += dp[i + 1]
        ans += dp[0]
        ans %= kMod

    return ans