Unique Length-3 Palindromic Subsequences

Leetcode  Problem with Code

Introduction: Counting Unique Length-3 Palindromic Subsequences

In this blog post, we will solve the problem of counting unique length-3 palindromic subsequences in a given string using an optimized Python solution. Palindromic subsequences are strings that read the same forwards and backwards, and our task is to find all unique such subsequences of length 3 in the given string. This problem can be efficiently solved with a method that leverages the positions of characters within the string.

Problem Understanding: What Are Palindromic Subsequences?

Before we dive into the solution, let’s break down the core concepts:

• Palindrome: A palindrome is a sequence that reads the same forwards and backwards. For example, “aba” and “cdc” are palindromes, but “abc” is not.
• Subsequence: A subsequence is a sequence derived from another sequence by deleting some elements without changing the order of the remaining elements. For instance, “ace” is a subsequence of “abcde”.

We are interested in counting all the unique length-3 palindromic subsequences within a string.

Example Walkthrough

Let’s take an example to understand the problem better:

Input: s = "aabca"

Step 1: Identify potential palindromic subsequences of length 3.

• “aba” (subsequence of “aabca”)
• “aca” (subsequence of “aabca”)
• “aaa” (subsequence of “aabca”)

So, the output should be 3 unique palindromic subsequences.

Input: s = "bbcbaba"

Step 2: Identify potential palindromic subsequences.

• “bbb”
• “bcb”
• “bab”
• “aba”

The output should be 4 unique palindromic subsequences.

The Python Solution

Here’s an efficient solution that counts the unique palindromic subsequences of length 3:

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

        for i, char in enumerate(s):
            first[ord(char) - ord('a')] = min(first[ord(char) - ord('a')], i)
            last[ord(char) - ord('a')] = i

        for i in range(26):
            if first[i] < last[i]:
                result += len(set(s[first[i] + 1:last[i]]))

        return result

Detailed Explanation:

1. Initialization:
   • first: This array keeps track of the first occurrence of each character in the string. It is initialized to a large value (float('inf')) for each character, as we want to store the smallest index for each character.
   • last: This array keeps track of the last occurrence of each character. It is initialized to -1 for each character, indicating that no character has been encountered initially.
   • result: This variable will hold the total count of unique palindromic subsequences.
2. Iterating through the string:
   • The string is processed once (for i, char in enumerate(s)), and for each character, we update the first and last arrays.
     • first[ord(char) - ord('a')] stores the smallest index where character char appears.
     • last[ord(char) - ord('a')] stores the largest index where character char appears.

   The reason we use ord(char) - ord('a') is to convert the character to its corresponding index in the alphabet (e.g., ‘a’ becomes 0, ‘b’ becomes 1, …, ‘z’ becomes 25).

3. Checking for valid subsequences:
   • We then iterate over each character (from ‘a’ to ‘z’ represented by indices 0 to 25).
   • For each character i, we check if first[i] < last[i]. This condition ensures that the character i appears at least twice in the string (once at first[i] and once at last[i]), meaning it could potentially form the first and third characters of a palindromic subsequence.
   • If the character appears more than once, we check the substring between first[i] + 1 and last[i] (exclusive). This substring contains all characters that can be the middle character of the palindromic subsequence. We use set to count only the unique characters between first[i] and last[i].
4. Final count:
   • The result variable accumulates the number of unique middle characters for each possible palindromic subsequence.
   • The function returns the total number of unique palindromic subsequences of length 3.

Example Walkthrough:

Input: "aabca"

1. First and Last Occurrences:
   • For 'a': first[0] = 0, last[0] = 4.
   • For 'b': first[1] = 1, last[1] = 3.
   • For 'c': first[2] = 2, last[2] = 2.
2. Counting Palindromic Subsequences:
   • For 'a': We check the substring s[1:4] (i.e., "abc"), the unique characters are {'b', 'c'}. So, there are 2 palindromic subsequences formed with 'a' as the first and last character: "aba" and "aca".
   • For 'b': We check the substring s[2:3] (i.e., "c"), the unique character is {'c'}, so the palindromic subsequence is "bcb".
3. Result: The unique palindromic subsequences are "aba", "aca", and "bcb", so the output is 3.

Input: "bbcbaba"

1. First and Last Occurrences:
   • For 'b': first[1] = 0, last[1] = 6.
   • For 'c': first[2] = 2, last[2] = 3.
   • For 'a': first[0] = 1, last[0] = 5.
2. Counting Palindromic Subsequences:
   • For 'b': We check the substring s[1:6] (i.e., "bcbab"), the unique characters are {'c', 'a', 'b'}. So, there are 3 palindromic subsequences formed with 'b' as the first and last character: "bbb", "bcb", "bab".
   • For 'a': We check the substring s[2:5] (i.e., "cba"), the unique characters are {'b', 'c'}, so the palindromic subsequence is "aba".
3. Result: The unique palindromic subsequences are "bbb", "bcb", "bab", and "aba", so the output is 4.

Time and Space Complexity:

• Time Complexity: O(n + 26):
  • O(n) to compute the first and last occurrences (where n is the length of the string).
  • O(26) to iterate over the alphabet and count the unique characters in each valid substring. Since the alphabet size is fixed (26), this part is constant.
• Space Complexity: O(1):
  • We use a fixed-size array of 26 elements for the first and last arrays.
  • The set used to store unique middle characters can grow to at most n, but since the array size is fixed, the overall space complexity is constant.

Count all triplets with given sum in sorted array