Unique Length 3 Palindromic Subsequences - Leetcode Solution

Problem Statement:

Given a string s, return the number of unique palindromic subsequences of length three that are a subsequence of s.

A subsequence of a string is a new string generated by deleting some characters of the original string without changing its relative order. Palindromic subsequences are subsequences that read the same backward as forward.

Example 1:

Input: s = "aabca" Output: 3 Explanation: The 3 Palindromic subsequences of length 3 are "aba","aaa" and "aca".

Solution:

Let's say we take two pointers, i and j, such that i points to the first character and j points to the last character of the string s.

Now, we want to find the count of unique length 3 palindromic subsequences. So, in order to do that, we can fix the middle character of the 3-character palindrome.

For every middle character, we will check how many palindromic subsequences we can form.

So, for every middle character, we will move i to the left and j to the right and check if the characters at those indices form a palindrome with the middle character.

Let's say the middle character is s[k]. We will check for all i < k and j > k, if s[i], s[k] and s[j] form a palindrome.

If s[i] == s[j] and s[i] != s[k], then we can form two palindromic subsequences of length 3, namely s[i]s[k]s[j] and s[j]s[k]s[i]. This is because we can interchange the first and last characters of a palindrome and still have a palindrome.

If s[i] == s[j] == s[k], then we can form only one palindromic subsequence of length 3, namely s[i]s[k]s[j].

We need to keep track of all the palindromic subsequences we are forming, so that we can eliminate duplicates.

For this, we can use a set. We will keep adding all the palindromic subsequences we find in the set.

Finally, we will return the size of the set as our answer.

Let's take an example to see how this works.

Example:

s = "aabca"

We start with i = 0 and j = 4 (the indices of the first and last character of the string).

We fix the middle character as s[2], which is 'b'.

We check all the pairs of indices (i, j) such that i < 2 and j > 2.

The first pair we check is (0, 4). Here, we have s[0] = 'a', s[2] = 'b' and s[4] = 'a'. These three characters do not form a palindrome. So, we move on to the next pair.

The next pair we check is (0, 3). Here, we have s[0] = 'a', s[2] = 'b' and s[3] = 'c'. These three characters do not form a palindrome. So, we move on to the next pair.

The next pair we check is (1, 4). Here, we have s[1] = 'a', s[2] = 'b' and s[4] = 'a'. These three characters form the palindrome 'aba'. So, we add this to our set.

The next pair we check is (1, 3). Here, we have s[1] = 'a', s[2] = 'b' and s[3] = 'c'. These three characters do not form a palindrome. So, we move on to the next pair.

The next pair we check is (2, 4). Here, we have s[2] = 'b', s[2] = 'b' and s[4] = 'a'. These three characters form the palindrome 'bab'. So, we add this to our set.

The next pair we check is (2, 3). Here, we have s[2] = 'b', s[2] = 'b' and s[3] = 'c'. These three characters do not form a palindrome. So, we move on to the next pair.

We have checked all possible pairs and found two palindromic subsequences of length 3: 'aba' and 'bab'.

So, the output is 2.

The above logic can be implemented in the following Python code:

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

    for k in range(1, len(s) - 1):
        left = 0
        right = len(s) - 1
        
        while left < k and right > k:
            if s[left] == s[right] and s[left] != s[k]:
                result_set.add(s[left] + s[k] + s[right])
                result_set.add(s[right] + s[k] + s[left])
            elif s[left] == s[right] == s[k]:
                result_set.add(s[left] + s[k] + s[right])
            
            left += 1
            right -= 1
            
    return len(result_set)

Time Complexity: O(n^2) Space Complexity: O(n^2)

1