# https://leetcode.com/problems/unique-length-3-palindromic-subsequences

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        first, last = {}, {}
        for i in range(len(s)):
            if s[i] not in first:
                first[s[i]] = i
            last[s[i]] = i
        palinedromes = set()
        for ch in first:
            i = first[ch]
            j = last[ch]
            if i + 1 < j:
                middles = s[i + 1 : j]
                for middle in middles:
                    palinedromes.add(''.join([ch, middle, ch]))
        return len(palinedromes)