2484. Count Palindromic Subsequences

Problem

Given a string of digits s, return **the number of *palindromic subsequences* of** s** having length **5. Since the answer may be very large, return it *modulo* 109 + 7.

Note:

• A string is palindromic if it reads the same forward and backward.

• A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

  Example 1:

Input: s = "103301"
Output: 2
Explanation: 
There are 6 possible subsequences of length 5: "10330","10331","10301","10301","13301","03301". 
Two of them (both equal to "10301") are palindromic.

Example 2:

Input: s = "0000000"
Output: 21
Explanation: All 21 subsequences are "00000", which is palindromic.

Example 3:

Input: s = "9999900000"
Output: 2
Explanation: The only two palindromic subsequences are "99999" and "00000".

  Constraints:

• 1 <= s.length <= 104

• s consists of digits.

Solution (Java)

class Solution {
    private static final int M = 1_000_000_000 + 7;

    public int countPalindromes(String s) {
        int n = s.length();
        long totalCount = 0;

        // for palindromes of the form "cd.dc", we will check
        // every possible combination of "cd" from "00" to "99"
        for (char c = '0'; c <= '9'; c++) {
            for (char d = '0'; d <= '9'; d++) {

                // number of combinations of "cd." up to each index (inclusive)
                long[] startCount = new long[n];

                // number of combinations of "cd"
                long cBeforeD = 0;

                // number of "c"
                long cCount = 0;

                // scan forwards to populate startCount
                for (int i = 0; i < n; i++) {
                    startCount[i] = cBeforeD;

                    // use multiple if instead of if/else for when c == d
                    char ch = s.charAt(i);
                    if (ch == d) {
                        cBeforeD += cCount;
                    }
                    if (ch == c) {
                        cCount++;
                    }
                }

                // reset counts
                cBeforeD = 0;
                cCount = 0;

                // scan backwards to update totalCount, stop at i == 3
                // because startCount counts the first 3 characters "cd."
                for (int i = n - 1; i >= 3; i--) {
                    char ch = s.charAt(i);
                    if (ch == d) {
                        cBeforeD += cCount;
                    }
                    if (ch == c) {
                        cCount++;
                    }

                    // the update to totalCount is the number of combinations of "dc"
                    // encountered so far multiplied by the number of combinations
                    // of "cd." up to index i - 1
                    totalCount = (totalCount + cBeforeD * startCount[i - 1]) % M;
                }
            }
        }

        return (int)totalCount;
    }
}

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).