Unique Length-3 Palindromic Subsequences

medium string hashing

Problem

Return the number of distinct length-3 palindromic subsequences of s. Palindromes have the form c·x·c.

Inputs = "aabca"

Output3

"aaa", "aba", "aca".

def count_palindromic_subsequence(s):
    total = 0
    for c in set(s):
        first = s.find(c)
        last = s.rfind(c)
        if last > first + 1:
            total += len(set(s[first + 1:last]))
    return total

function countPalindromicSubsequence(s) {
  let total = 0;
  for (const c of new Set(s)) {
    const first = s.indexOf(c), last = s.lastIndexOf(c);
    if (last > first + 1) total += new Set(s.slice(first + 1, last)).size;
  }
  return total;
}

class Solution {
    public int countPalindromicSubsequence(String s) {
        int total = 0;
        for (char c = 'a'; c <= 'z'; c++) {
            int first = s.indexOf(c), last = s.lastIndexOf(c);
            if (last > first + 1) {
                Set<Character> set = new HashSet<>();
                for (int i = first + 1; i < last; i++) set.add(s.charAt(i));
                total += set.size();
            }
        }
        return total;
    }
}

int countPalindromicSubsequence(string s) {
    int total = 0;
    for (char c = 'a'; c <= 'z'; c++) {
        size_t first = s.find(c), last = s.rfind(c);
        if (first == string::npos || last == first) continue;
        if (last > first + 1) {
            unordered_set<char> set;
            for (size_t i = first + 1; i < last; i++) set.insert(s[i]);
            total += set.size();
        }
    }
    return total;
}

Explanation

A length-3 palindrome has the shape c·x·c — the same letter on both ends and any letter in the middle. The clever insight is that we only need to fix the outer letter and count how many distinct middles are possible.

For each letter c that appears, the best chance to wrap a middle is to use its first and last occurrence as the two ends, because that window is the widest. We grab first = s.find(c) and last = s.rfind(c).

If there is room between them (last > first + 1), every distinct character strictly between those positions can be the middle, giving a unique palindrome. So we count the distinct chars in s[first+1:last] using a set and add that to total.

Using the outermost pair guarantees we see the most middle options, and the set removes duplicates so we count each palindrome only once. Summing over all 26 letters gives the answer.

Example: "aabca". For a, first is index 0 and last is index 4, and the middles between them are {a, b, c}, which is 3 distinct letters → "aaa", "aba", "aca". No other letter contributes, so the total is 3.

Time: O(26·n) Space: O(26)