Count the number of distinct palindromic subsequences of length 3 in a string.
Given a string s, count how many distinct subsequences of length 3 are palindromes.
A subsequence is formed by deleting zero or more characters without changing the order of the remaining characters. A length-3 subsequence is palindromic if it has the form x y x, where the first and third characters are the same.
Two subsequences are considered distinct if their resulting strings are different, even if they were chosen from different positions in s.
Your task is to return the number of distinct palindromic subsequences of length 3 in s.
s.3.s contains only lowercase English letters.Example 1
Input
s = "aabca"
Output
3
Explanation
The distinct length-3 palindromic subsequences are "aaa", "aba", and "aca".
Example 2
Input
s = "adc"
Output
0
Explanation
There is no length-3 subsequence of the form x y x.
Example 3
Input
s = "bbcbaba"
Output
4
Explanation
The distinct palindromic subsequences of length 3 are "bbb", "bcb", "bab", and "aba".
Premium problem context
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.