Leetcode 2484. Count Palindromic Subsequences

[Woodyiiiiiii]

这道题我一点思路都没有...

tips:

1. 数组长度为10^4，而O(n^2)时间复杂度勉强够。
2. 注意取模的时候，如果超过一次运算(比如res+=(a*b))，最好先用long存着，再mod

正解：分解5为'2+1+1'，O(n)时间复杂度
'2+1+2' DP:

class Solution {
    public int countPalindromes(String s) {
        int len = s.length();
        // split 5 to 2 + 1 + 2
        int[][] left = new int[len][100];
        int[][] right = new int[len][100];
        final int mod = 1000000007;

        // left[i][j] means the number of j(0~99) at index i
        int[] numberCnt = new int[10];
        for (int i = 0; i < len; ++i) {
            int num = s.charAt(i) - '0';
            for (int j = 0; j < 10; ++j) {
                left[i][j * 10 + num] = numberCnt[j];
            }
            // accumulate
            if (i != 0) {
                for (int k = 0; k < 100; ++k) {
                    left[i][k] += left[i - 1][k];
                }
            }
            numberCnt[num]++;
        }

        // right[i][j] means the number of j(0~99) at index i
        numberCnt = new int[10];
        for (int i = len - 1; i >= 0; --i) {
            int num = s.charAt(i) - '0';
            for (int j = 0; j < 10; ++j) {
                right[i][j * 10 + num] = numberCnt[j];
            }
            if (i != len - 1) {
                for (int k = 0; k < 100; ++k) {
                    right[i][k] += right[i + 1][k];
                }
            }
            numberCnt[num]++;
        }

        // middle number(0~9)
        long ans = 0;
        for (int i = 2; i < len - 2; ++i) {
            for (int k = 0; k < 100; ++k) {
                // number is left * middle * right
                ans += ((long) left[i - 1][k] * right[i + 1][k]);
                ans %= mod;
            }
        }

        return (int) ans;
    }
}

'3+2' DP:

class Solution {
    public int countPalindromes(String s) {
        char[] map = s.toCharArray();

        int MOD = 1000000007;

        int[][] dp = new int[2][s.length()];   // dp[i][j] 表示 [i,j] 这个里面的3回文数量。 dp[i][j] = dp[i][j-1] + (s[i] == s[j] ? j - i - 1 : 0)

        int res = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            int tempI = i % 2;
            int beforeI = (tempI + 1) % 2;
            for (int j = i + 2; j < s.length(); j++) {
                dp[tempI][j] = (dp[tempI][j - 1] + dp[beforeI][j] - dp[beforeI][j - 1] + MOD) % MOD + (map[i] == map[j] ? j - i - 1 : 0);
                dp[tempI][j] %= MOD;
                if (map[i] == map[j] && j - i >= 4) {
                    res += dp[beforeI][j - 1];
                    res %= MOD;
                }
            }
        }

        return res;

    }
}

一个月后，我重新做了这道题，按照2+1+2DP的做法：

class Solution {
    public int countPalindromes(String s) {
        final int MOD = (int) (1e9 + 7);
        long ans = 0;
        int n = s.length();
        if (n < 5) {
            return 0;
        }

        // init
        long[][] prefixUnits = new long[n][10];
        long[][] suffixUnits = new long[n][10];
        for (int i = 1; i < n; i++) {
            System.arraycopy(prefixUnits[i - 1], 0, prefixUnits[i], 0, 10);
            prefixUnits[i][s.charAt(i - 1) - '0']++;
        }
        for (int i = n - 2; i >= 0; i--) {
            System.arraycopy(suffixUnits[i + 1], 0, suffixUnits[i], 0, 10);
            suffixUnits[i][s.charAt(i + 1) - '0']++;
        }

        // calculate dp
        long[][] prefixDp = new long[n][100];
        long[][] suffixDp = new long[n][100];
        int firstNum = (s.charAt(0) - '0') * 10 + (s.charAt(1) - '0');
        int lastNum = (s.charAt(n - 1) - '0') * 10 + (s.charAt(n - 2) - '0');
        prefixDp[2][firstNum] = 1;
        suffixDp[n - 3][lastNum] = 1;
        for (int i = 2; i < n - 2; ++i) {
            for (int j = 0; j < 100; ++j) {
                prefixDp[i][j] += prefixDp[i - 1][j];
            }
            int cur = s.charAt(i) - '0';
            for (int j = 0; j < 10; ++j) {
                if (prefixUnits[i][j] == 0) {
                    continue;
                }
                int num = j * 10 + cur;
                prefixDp[i + 1][num] += prefixUnits[i][j];
            }
        }
        for (int i = n - 3; i >= 2; --i) {
            for (int j = 0; j < 100; ++j) {
                suffixDp[i][j] += suffixDp[i + 1][j];
            }
            int cur = s.charAt(i) - '0';
            for (int j = 0; j < 10; ++j) {
                if (suffixUnits[i][j] == 0) {
                    continue;
                }
                int num = j * 10 + cur;
                suffixDp[i - 1][num] += suffixUnits[i][j];
            }
        }

        for (int i = 2; i < n - 2; ++i) {
            for (int j = 0; j < 100; ++j) {
                if (prefixDp[i][j] == 0 || suffixDp[i][j] == 0) {
                    continue;
                }
                ans += prefixDp[i][j] * suffixDp[i][j];
                ans %= MOD;
            }
        }
        return (int) ans;
    }
}

这种奇数次回旋字符串数目类型的题目都可以按照类似的解法——分回旋字符串为两种类型，然后分成两截进行DP计算。类似题目有：

• 2222. Number of Ways to Select Buildings
• 2217. Find Palindrome With Fixed Length

---

• https://leetcode.com/problems/count-palindromic-subsequences/