LeetCode Solutions

			

class Solution {
 public:
  int countPalindromicSubsequences(string s) {
    constexpr int kMod = 1'000'000'007;
    const int n = s.length();

    // dp[i][j] := # of different non-empty palindromic subseqs in s[i..j]
    vector<vector<int>> dp(n, vector<int>(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];
  }
};

			

class Solution {
  public int countPalindromicSubsequences(String s) {
    final int kMod = 1_000_000_007;
    final int n = s.length();

    // dp[i][j] := # of different non-empty palindromic subseqs 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];
  }
}

			

class Solution:
  def countPalindromicSubsequences(self, s: str) -> int:
    def count(l: int, r: int) -> int:
      if l > r:
        return 0
      if l == r:
        return 1
      key = l * len(s) + r
      if key in memo:
        return memo[key]

      if s[l] == s[r]:
        lo = l + 1
        hi = r - 1
        while lo <= hi and s[lo] != s[l]:
          lo += 1
        while lo <= hi and s[hi] != s[l]:
          hi -= 1
        if lo > hi:
          ans = count(l + 1, r - 1) * 2 + 2
        elif lo == hi:
          ans = count(l + 1, r - 1) * 2 + 1
        else:
          ans = count(l + 1, r - 1) * 2 - count(lo + 1, hi - 1)
      else:
        ans = count(l, r - 1) + count(l + 1, r) - count(l + 1, r - 1)

      memo[key] = (ans + kMod) % kMod
      return memo[key]

    kMod = 1_000_000_007
    memo = {}

    return count(0, len(s) - 1)