Problem of The Day: Unique Length-3 Palindromic Subsequences

Problem Statement

Brute Force [TLE]

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

        def isPalindrome(curr):
            l, r = 0, len(curr) - 1
            while l < r:
                if curr[l] != curr[r]:
                    return False
                l += 1
                r -= 1
            return True

        def dfs(i, curr):
            if i == N:
                if len(curr) == 3 and isPalindrome(curr):
                    seen.add(''.join(curr))
                return
            if len(curr) == 3:
                if isPalindrome(curr):
                    seen.add(''.join(curr))
                return
            dfs(i + 1, curr + [s[i]])
            dfs(i + 1, curr)


        for i in range(N):
            dfs(i, [])

        return len(seen)

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        N = len(s)
        pos = defaultdict(int)
        res = set()
        for i, c in enumerate(s):
            if i >= 2 and c in pos:
                for j in range(pos[c] + 1, i):
                    res.add(c + s[j] + c)
            if c not in pos:
                pos[c] = i
        return len(res)

Improve Algorithm using first and last

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        # Track the first and last occurrence of each character
        first = {}
        last = {}

        for i, c in enumerate(s):
            if c not in first:
                first[c] = i
            last[c] = i

        res = set()

        # Iterate over all characters in the string
        for c in first:
            if last[c] - first[c] > 1:  # Check if there's space for a middle character
                # Add all unique middle characters
                res.update({c + s[mid] + c for mid in range(first[c] + 1, last[c])})

        return len(res)

Editorial

Approach 1: Count Letters In-Between

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

        for letter in letters:
            i, j = s.index(letter), s.rindex(letter)
            between = set()

            for k in range(i + 1, j):
                between.add(s[k])

            ans += len(between)

        return ans

Python 1-liner:

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        return sum([len(set(s[s.index(letter)+1:s.rindex(letter)])) for letter in set(s)])

Approach 2: Pre-Compute First and Last Indices

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        first = [-1] * 26
        last = [-1] * 26

        for i in range(len(s)):
            curr = ord(s[i]) - ord("a")
            if first[curr] == -1:
                first[curr] = i

            last[curr] = i

        ans = 0
        for i in range(26):
            if first[i] == -1:
                continue

            between = set()
            for j in range(first[i] + 1, last[i]):
                between.add(s[j])

            ans += len(between)

        return ans

• time: O(n)
• space: O(1)