Count the number of distinct palindromic subsequences of length 3 in a string.
Unique Length-3 Palindromic Subsequences
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.
Input Format
- A single string
s.
Output Format
- Return an integer: the number of distinct palindromic subsequences of length
3.
Constraints
scontains only lowercase English letters.- The answer fits in a 32-bit signed integer.
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.
Show 1 more example
Example 3
Input
s = "bbcbaba"
Output
4
Explanation
The distinct palindromic subsequences of length 3 are "bbb", "bcb", "bab", and "aba".
Premium problem context
Unlock deeper context for this problem
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.