DDSA Solutions

1930. Unique Length-3 Palindromic Subsequences

MediumView on LeetCode
Hash TableStringPrefix Sum
Time: O(26n)
Space: O(1)

Problem Overview

Count distinct palindromic subsequences of length 3.

Intuition

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

Algorithm

  1. 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
C#
// 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?

Related Problems