Today’s problem

https://leetcode.com/problems/unique-length-3-palindromic-subsequences/description/

Intuition

Because the question requires the count of unqiue subsequence. Therefore, the largest count is $26*26 = 676$. Therefore, all we have to do is to count how many unique characters are there between two same characters.

Approach

First we need to calculate the first and last occurance of a character. Then we need to iterate between l and r to count how many unique characters are there between l and r.

Complexity

• Time complexity: $O(kN)$, k is the number of unique characters, here it means 26 different character. N is the length of the string.

• Space complexity: $O(N)$

Code

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        st = [inf] * 26
        en = [-1] * 26
        a = ord('a')
        for i,ch in enumerate(s):
            nch = ord(ch) - a
            st[nch] = min(st[nch], i)
            en[nch] = max(en[nch], i)

        ans = 0

        for x in range(26):
            if en[x] <= st[x]:
                continue
            # print(en[x], st[x], x)
            vis = set([])
            for i in range(st[x] + 1, en[x]):
                vis.add(s[i])
            ans += len(vis)

        return ans