Back to solutions

Unique Length 3 Palindromic Subsequences

MediumArrays

Count distinct palindromic subsequences of length three.

Open problem
Constraints
  • 3 <= length <= 10^5
  • lowercase English letters

First and last occurrence per letter

Time O(26 * n)Space O(1)

A length-3 palindrome x?x is determined by the outer letter x and the middle letter. For each letter x, the widest span is between its first and last occurrence; any distinct character strictly between them can be the middle. So count distinct characters between the first and last occurrence of each letter and sum those counts.

Key terms
subsequence:
Characters kept in order but not necessarily contiguous.
first/last occurrence:
The outermost positions of a letter, which bound the possible middle characters.
int countPalindromicSubsequence(const string& s) {
    int first[26], last[26];
    fill(first, first + 26, -1); fill(last, last + 26, -1);
    for (int i = 0; i < (int)s.size(); i++) {
        int c = s[i] - 'a';
        if (first[c] == -1) first[c] = i;
        last[c] = i;
    }
    int total = 0;
    for (int c = 0; c < 26; c++) {
        if (first[c] == -1 || last[c] - first[c] < 2) continue;
        set<char> mid;
        for (int i = first[c] + 1; i < last[c]; i++) mid.insert(s[i]);
        total += mid.size();
    }
    return total;
}
Step by step
  1. Record the first and last index of each of the 26 letters.
  2. For each letter with last - first >= 2, look at the characters strictly between them.
  3. Count the distinct middle characters; each forms a unique palindrome with this outer letter.
  4. Sum these counts over all letters.