Unique Length-3 Palindromic Subsequences

Count the number of distinct length-3 palindromic subsequences in s — i.e., unique strings of the form "a b a" that can be formed as subsequences. The key observation is that each palindrome is determined by a matching outer character and a middle character, so you can count, for each letter that appears at least twice, the distinct characters occurring between its occurrences.