1930. Unique Length-3 Palindromic Subsequences

Time: O(26n)

Space: O(1)

Intuition

Count distinct palindromic subsequences of length 3. Fix the two outer characters (same) and count distinct inner characters.

Algorithm

1For each character c (a-z): find first and last occurrence. Count distinct chars strictly between them.

Common Pitfalls

•Palindrome of length 3: c_middle_c. For each outer char, count distinct inner chars (not duplicates).

1930.cs

// Approach: For each char find first/last occurrence; count distinct chars between them as middle.
// Time: O(26n) Space: O(1)

public class Solution
{
    public int CountPalindromicSubsequence(string s)
    {
        int ans = 0;
        int[] first = new int[26];
        int[] last = new int[26];

        Array.Fill(first, s.Length);

        for (int i = 0; i < s.Length; ++i)
        {
            int index = s[i] - 'a';
            first[index] = Math.Min(first[index], i);
            last[index] = i;
        }

        for (int i = 0; i < 26; ++i)
        {
            if (first[i] < last[i])
                ans += s.Substring(first[i] + 1, last[i] - first[i] - 1).Distinct().Count();
        }

        return ans;
    }
}

Was this solution helpful?