Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Every length-three palindrome has the form c?c. For a fixed outer character, its first and last occurrences enclose every middle position that could participate in such a subsequence. Each distinct middle character creates exactly one distinct palindrome.

Approach

For each lowercase letter, locate its first and last positions. If they are distinct, collect the characters strictly between them in a set and add the set size to the answer. Missing or singly occurring outer letters contribute nothing. Return the sum over all outer letters. Using character sets counts unique palindrome strings, not the potentially much larger number of index triples producing them.

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        res = 0

        for i in range(26):
            c = chr(i + ord('a'))
            left = s.find(c)
            right = s.rfind(c)
            if left != -1 and left < right:
                res += len(set(s[left + 1 : right]))

        return res

Complexity analysis

Let n = s.length. Time: O(26n) = O(n) for first/last searches and distinct-middle scans. Auxiliary space: O(n) for the largest sliced substring and set.