LeetCode/cs/unique-length-3-palindromic-subsequences.cs

public class Solution {
    private static readonly int NOT_FOUND = int.MaxValue;

    public int CountPalindromicSubsequence(string s) {
        var (first, last) = (new int[26], new int[26]);
        Array.Fill(first, NOT_FOUND);

        // Initialize the indices
        for (var i = 0; i < s.Length; ++i) {
            var idx = s[i] - 'a';
            first[idx] = Math.Min(first[idx], i);
            last[idx] = i;
        }

        var count = 0;
        for (var c = 0; c < 26; ++c) {
            if (first[c] == NOT_FOUND) {
                continue;
            }

            var between = new HashSet<char>();
            for (int i = first[c] + 1; i < last[c]; ++i) {
                between.Add(s[i]);
            }

            count += between.Count;
        }

        return count;
    }
}