# 1930. Unique Length-3 Palindromic Subsequences

## Description

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: 3
Explanation: The 3 palindromic subsequences of length 3 are:
- "aba" (subsequence of "aabca")
- "aaa" (subsequence of "aabca")
- "aca" (subsequence of "aabca")


Example 2:

Input: s = "adc"
Output: 0
Explanation: There are no palindromic subsequences of length 3 in "adc".


Example 3:

Input: s = "bbcbaba"
Output: 4
Explanation: The 4 palindromic subsequences of length 3 are:
- "bbb" (subsequence of "bbcbaba")
- "bcb" (subsequence of "bbcbaba")
- "bab" (subsequence of "bbcbaba")
- "aba" (subsequence of "bbcbaba")


Constraints:

• 3 <= s.length <= 105
• s consists of only lowercase English letters.

## Solutions

• class Solution {
public int countPalindromicSubsequence(String s) {
int ans = 0;
for (char c = 'a'; c <= 'z'; ++c) {
int l = s.indexOf(c), r = s.lastIndexOf(c);
Set<Character> cs = new HashSet<>();
for (int i = l + 1; i < r; ++i) {
}
ans += cs.size();
}
return ans;
}
}

• class Solution {
public:
int countPalindromicSubsequence(string s) {
int ans = 0;
for (char c = 'a'; c <= 'z'; ++c) {
int l = s.find_first_of(c), r = s.find_last_of(c);
unordered_set<char> cs;
for (int i = l + 1; i < r; ++i) cs.insert(s[i]);
ans += cs.size();
}
return ans;
}
};

• class Solution:
def countPalindromicSubsequence(self, s: str) -> int:
ans = 0
for c in ascii_lowercase:
l, r = s.find(c), s.rfind(c)
if r - l > 1:
ans += len(set(s[l + 1 : r]))
return ans


• func countPalindromicSubsequence(s string) (ans int) {
for c := 'a'; c <= 'z'; c++ {
l, r := strings.Index(s, string(c)), strings.LastIndex(s, string(c))
cs := map[byte]struct{}{}
for i := l + 1; i < r; i++ {
cs[s[i]] = struct{}{}
}
ans += len(cs)
}
return
}

• public class Solution {
public int CountPalindromicSubsequence(string s) {
int ans = 0;
for (char c = 'a'; c <= 'z'; ++c) {
int l = s.IndexOf(c), r = s.LastIndexOf(c);
HashSet<char> cs = new HashSet<char>();
for (int i = l + 1; i < r; ++i) {