730. Count Different Palindromic Subsequences

09/19/2021

Leetcode

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'.

Basic Idea

General的DP思路比较复杂，也有太多的edge case需要考虑，可以看花花酱的视频，但我个人觉得在面试中写出来难度太大，所以这里来记录另一种DP思路。

考虑到所给的字母范围是比较小的，只有 abcd，不难想到利用有限的字母以及他们的index来做文章。这种思路就是从外层先开始考虑，每次考虑一种字母，例如最外层考虑a...a, b....b, c.....c, d...d的情况，然后例如对于 a....a下一层考虑 a...a...a...a, a...b...b...a ... 的情况。例如对于题目中的例子 bccb ，最外层的循环考虑 bb有2种(b, bb)，cc有两种(c, cc)，然后对于b...b的情况，下一层考虑了(bccb)和(bcb)共有两种，一共6种。

Java Code:

class Solution {
    int MOD = (int) 1e9 + 7;
    String s;
    int N;
    int[][] dp;
    Map<Character, TreeSet<Integer>> charMap;
    
    public int countPalindromicSubsequences(String s) {
        this.N = s.length();
        this.s = s;
        dp = new int[N][N];
        charMap = new HashMap<>();
        for (char c = 'a'; c <= 'd'; ++c) {
            charMap.put(c, new TreeSet<>());
        }
        for (int i = 0; i < s.length(); ++i) {
            charMap.get(s.charAt(i)).add(i);
        }
        return dfs(0, N - 1);
    }
    
    private int dfs(int left, int right) {
        if (left == right) return 1;
        if (dp[left][right] != 0) return dp[left][right];
        long count = 0;
        for (char c = 'a'; c <= 'd'; ++c) {
            Integer newLeft = charMap.get(c).ceiling(left);
            Integer newRight = charMap.get(c).floor(right);
            if (newLeft == null || newLeft > right) {
                // 只考虑左右边界内的
                continue;
            }
            count++; // 如果只有单个字母，则只能贡献1种
            if (newLeft < newRight) {
                count++;
                // 这里的下一层的意义是包含了当前字母作为外层的组合数量
                // 例如bccb的case，当前c==b时，接下来的dfs算出的就是
                // bccb 和 bcb 两种组合
                count += dfs(newLeft + 1, newRight - 1);
            }
        }
        dp[left][right] = (int) (count % MOD);
        return dp[left][right];
    }
}