1930. Unique Length-3 Palindromic Subsequences

'''
Explanation
For each palindromes in format of "aba",
we enumerate the character on two side.

We find its first occurrence and its last occurrence,
all the characters in the middle are the candidate for the midd char.


Complexity
Time O(26n)
Space O(26n)


'''
class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        ans=0
        for i in range(26):
            ch=chr(ord('a')+i)
            l,r=s.find(ch),s.rfind(ch)
            if r-l>1:
                ans+=len(set(s[l+1:r]))
        return ans