Unique Length-3 Palindromic Subsequences

main.md

Question

Approaches

Approach 1

My first approach was to map out all the unique palindromes of length three using three nested loops. I then maintained a set to store the results, ensuring each palindrome was counted only once.

To check for all valid palindromes, I iterated through the string s using three indices (i, j, k), where (i < j < k). For each triplet, I checked if the characters at indices (i) and (k) matched, as this is the necessary condition for a length-3 palindrome. If they matched, I formed the subsequence using (s[i]), (s[j]), and (s[k]) and added it to the set of results.

Finally, after processing all combinations, I returned the size of the set, which gave the count of unique palindromes.

Yes, this works. But it's not efficient, as I encountered performance issues (TLE) on large inputs due to the O(n^3) complexity of the nested loops.

Implementation

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

        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    if s[i] == s[k]:
                        uniq_palindromes.add((s[i], s[j], s[k]))
        
        return len(uniq_palindromes)

Compleixities

• Time: O(n^3) because of the three nested loops
• Space: O(p) where p ≤ 676

Approach 2

My optimized approach was to use the prefix and suffix arrays to count unique palindromic subsequences.

First, I created two arrays: prefix and suffix. The prefix array stores the set of characters seen so far from the start of the string up to each position, while the suffix array stores the set of characters seen so far from the end of the string up to each position.

To check for palindromes, I iterated through each character in the string as the middle of the palindrome. For each middle character, I checked the prefix array to find eligible characters that could form the start of the palindrome and the suffix array to find eligible characters that could form the end. If the same character was present in both the prefix and suffix arrays, I added the triplet to a set to ensure uniqueness.

Finally, after all characters were processed, I returned the size of the set as the result.

This works too but it's slow to an extent. I will further optimize when I fully grasp and revisit the question.

Implementation

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

        prefix = [set() for _ in range(n)]
        suffix = [set() for _ in range(n)]

        seen = set()
        for i in range(n):
            seen.add(s[i])
            prefix[i] = seen.copy()
        
        seen = set()
        for i in range(n - 1, -1, -1):
            seen.add(s[i])
            suffix[i] = seen.copy()

        uniq_palindromes = set()

        for j in range(1, n - 1):
            for c in prefix[j - 1]:
                if c in suffix[j + 1]:
                    uniq_palindromes.add((c, s[j], c))
        
        return len(uniq_palindromes)

Compleixities

• Time: O(n)
• Space: O(n+p), where p ≤ 676

First Kudos for solving this at both approach, saw some answers but still wasn't able to grasp it.