Problem Description

Given a string s consisting only of lowercase English letters, your task is to count the number of unique palindromic subsequences of length 3 that appear in s.
A palindromic subsequence is a sequence that reads the same forwards and backwards, and can be formed by deleting zero or more characters from s without changing the order of the remaining characters.
Specifically, you need to find all unique subsequences of the form c1 c2 c1 (where c1 and c2 are characters, and the two c1s can be at different positions), and count how many such unique ones exist in s.
Constraints:

• Each subsequence must be length 3.
• The first and last character must be the same.
• The middle character can be any character (including possibly the same as the outer character).
• Each unique combination is counted only once, regardless of how many times it appears in s.
• Characters must be chosen in order, but do not need to be contiguous.

Thought Process

The naive way to solve this problem would be to consider every possible triplet of positions in s and check if they form a palindrome of the form c1 c2 c1. However, this would be extremely inefficient for longer strings, as it would require checking all possible combinations of three characters, leading to a time complexity of O(n³).
To optimize, we observe that for a valid palindromic subsequence of length 3, we only care about:

• The character c1 (which must appear at least twice in s).
• The set of distinct characters c2 that appear between the first and last occurrence of c1.

Solution Approach

Let's break down the optimized algorithm step by step:

1. Record First and Last Occurrences:
   For each character from 'a' to 'z', scan through s to find the first and last index where it appears.
2. Collect Unique Middles:
   For every character c1 that appears at least twice, look at the substring between its first and last occurrence. For every character c2 that appears in this range, c1 c2 c1 forms a valid palindromic subsequence.
3. Count Unique Pairs:
   For each c1, keep a set of all possible c2s found between its first and last index. The total number of unique palindromic subsequences is the sum of all these sets' sizes.

• We only consider valid subsequences by construction.
• Sets ensure uniqueness.
• We avoid nested loops over all triplets, reducing time complexity significantly.

Example Walkthrough

Let's use the example s = "aabca":

• The character 'a' appears at indices 0, 1, and 4. The substring between the first and last 'a' is "abc" (indices 1 to 4, exclusive of the ends).
• The unique middle characters between the first and last 'a' are 'b' and 'c'. So, the palindromic subsequences are "aba" and "aca".
• Next, check 'b': it appears only once, so skip.
• Check 'c': it appears only once, so skip.

Time and Space Complexity

Brute-force approach:

• Time Complexity: O(n³), since you would check every triplet of indices.
• Space Complexity: O(1) (not counting result set).

• Time Complexity: O(26n), which simplifies to O(n), since for each of 26 letters, we scan the substring between first and last occurrence.
• Space Complexity: O(26*26), as for each character, we may store up to 26 middle characters.

Summary

The key insight is to recognize that for a length-3 palindrome, only the first and last character (which must be the same) and the set of unique middle characters matter. By precomputing the first and last occurrence of each character and examining the substring in between, we efficiently count all unique palindromic subsequences of the form c1 c2 c1 without redundancy. The use of sets ensures uniqueness, and the approach is optimal for the problem constraints.

Code Implementation

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        res = 0
        for c in set(s):
            first = s.find(c)
            last = s.rfind(c)
            if last - first > 1:
                middles = set(s[first+1:last])
                res += len(middles)
        return res
      

class Solution {
public:
    int countPalindromicSubsequence(string s) {
        int res = 0;
        for (char c = 'a'; c <= 'z'; ++c) {
            int first = s.find(c);
            int last = s.rfind(c);
            if (last - first > 1) {
                unordered_set<char> middles;
                for (int i = first + 1; i < last; ++i) {
                    middles.insert(s[i]);
                }
                res += middles.size();
            }
        }
        return res;
    }
};
      

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

var countPalindromicSubsequence = function(s) {
    let res = 0;
    for (let code = 97; code <= 122; ++code) {
        let c = String.fromCharCode(code);
        let first = s.indexOf(c);
        let last = s.lastIndexOf(c);
        if (last - first > 1) {
            let middles = new Set();
            for (let i = first + 1; i < last; ++i) {
                middles.add(s[i]);
            }
            res += middles.size;
        }
    }
    return res;
};