0730. Count Different Palindromic Subsequences

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

Description

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

ac

class Solution {
    public int countPalindromicSubsequences(String S) {
        // edge cases
        if (S == null || S.length() == 0) return 0;

        int n = S.length();
        // long[][] dp = new long[n][n];
        int[][] dp = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = i; j >= 0; j--) {
                if (S.charAt(j) == S.charAt(i)) {
                    if (j == i || j + 1 == i) {
                        dp[j][i] = i - j + 1;
                    } else {
                        // dedup
                        int l = j + 1, r = i - 1;
                        while (l <= r && S.charAt(l) != S.charAt(j)) l++;
                        while (r >= l && S.charAt(r) != S.charAt(i)) r--;

                        if (l > r) {  // no duplicate, bcb
                            dp[j][i] = 2 * dp[j+1][i-1] + 2;
                        } else if (l == r) {  // 1 duplicate, bcbcb
                            dp[j][i] = 2 * dp[j+1][i-1] + 1;
                        } else { // 2 duplicates, bcbbcb
                            dp[j][i] = 2 * dp[j+1][i-1] - dp[l+1][r-1];
                        }
                    }
                } else {
                    dp[j][i] = dp[j+1][i] + dp[j][i-1] - dp[j+1][i-1];
                }

                dp[j][i] = dp[j][i] < 0 ? dp[j][i] + 1000000007 : dp[j][i] % 1000000007; //why??
            }
        }

        return dp[0][n-1];
        // return (int) (dp[0][n-1] % 1000000007);
    }
}

/*
the key is dedup, and the way is so brilliant, never seen before
*/