Problem Statement in English

You’re given a string s consisting of lowercase English letters.

A length 3 palindromic subsequence is a subsequence of s that is a palindrome of length 3.

Return the number of unique length 3 palindromic subsequences in s.

Approach

The key observation is that a length 3 palindromic subsequence has the form “aba”, where ‘a’ and ‘b’ are characters from the string.

Particularly, the first and last characters must be the same, and the middle character can be any character that appears between the first and last occurrence of that character in the string.

So all we really need to do is, pick a character for the first and last position, find its first and last occurrence in the string, and count how many unique characters exist between those two positions.

That’s it!

Solution in Python


class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        chars = set(s)

        res = 0

        for char in chars:
            l = s.find(char)
            r = s.rfind(char)

            if l != r:
                res += len(set(s[l + 1:r]))

        return res

Complexity

  • Time: $O(n)$
    Since there can only be 26 unique characters, the outer loop runs at most 26 times. The find and rfind operations each take $O(n)$ time, and the slicing and set creation also take $O(n)$ time in the worst case. Thus, the overall time complexity is $O(26 * n) = O(n)$.

  • Space: $O(1)$
    Since there are only 26 lowercase English letters, the space used for the set of characters is constant, i.e., $O(1)$.

Mistakes I Made

I was storing stuff in a hashmap unnecessarily.

And we are done.