Unique Length-3 Palindromic Subsequences
Given a string s, return the number of unique palindromes of length three that are a subsequence of s.
Note that even if there are multiple ways to obtain the same subsequence, it is still only counted once.
A palindrome is a string that reads the same forwards and backwards.
A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.
- For example,
"ace"is a subsequence of"abcde".
Example 1
Input
s = "aabca"Output
3The 3 palindromic subsequences of length 3 are "aba", "aaa", and "aca".
Example 2
Input
s = "adc"Output
0There are no palindromic subsequences of length 3 in "adc".
Constraints
- 3 <= s.length <= 10^5
- s consists of only lowercase English letters.