LeetCode-in-Java
2484. Count Palindromic Subsequences
Hard
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 <= 104sconsists of digits.
Solution
public class Solution {
public int countPalindromes(String s) {
int n = s.length();
long ans = 0;
int mod = (int) 1e9 + 7;
int[] count = new int[10];
for (int i = 0; i < n; i++) {
long m = 0;
for (int j = n - 1; j > i; j--) {
if (s.charAt(i) == s.charAt(j)) {
ans += (m * (j - i - 1));
ans = ans % mod;
}
m += count[s.charAt(j) - '0'];
}
count[s.charAt(i) - '0']++;
}
return (int) ans;
}
}