Problem Description

You are given a string s and need to find how many unique palindromes of length three can be formed as subsequences from this string.

A palindrome is a string that reads the same forwards and backwards. For a palindrome of length three, it must have the pattern aba where the first and third characters are the same.

A subsequence is formed by taking characters from the original string while maintaining their relative order, but the characters don't need to be consecutive. For example, from the string "abcde", we can form the subsequence "ace" by taking the 1st, 3rd, and 5th characters.

The key requirements are:

• Each palindrome must be exactly 3 characters long
• The palindrome must be a subsequence (not necessarily consecutive characters)
• Count only unique palindromes - if the same palindrome can be formed in multiple ways, count it only once

For example, if s = "aabca":

• We can form "aaa" by choosing positions (0,1,4) or (0,2,4) - but this counts as just one unique palindrome
• We can form "aba" by choosing positions (0,2,4)
• We can form "aca" by choosing positions (0,3,4)
• Total unique palindromic subsequences of length 3: 3

The solution approach cleverly uses the fact that for any palindrome of length 3 with pattern aba, we need the same character a at both ends. So for each character c, we find its first occurrence at position l and last occurrence at position r. Any character between positions l and r can serve as the middle character to form a valid palindrome cXc. The number of unique characters between l and r gives us the count of unique palindromes with c as the end characters.

Intuition

To find unique palindromic subsequences of length 3, let's first think about what they look like. A palindrome of length 3 must have the form aba where the first and last characters are identical.

The key insight is that we don't need to check all possible combinations of three positions in the string. Instead, we can think about it differently: for any palindrome aba, we need to find two occurrences of the character a with at least one character between them.

This leads us to a clever observation: for each character that appears at least twice in the string, we can use its first and last occurrences as the "bookends" of our palindrome. Any character that appears between these two positions can serve as the middle character.

For example, if we have the string "abcbda" and we're looking at character 'a':

• First occurrence of 'a' is at index 0
• Last occurrence of 'a' is at index 5
• Between indices 0 and 5, we have characters: b, c, b, d
• The unique characters are: {b, c, d}
• So we can form 3 unique palindromes with 'a' as bookends: "aba", "aca", "ada"

Since we only have 26 lowercase letters, we can simply iterate through each letter from 'a' to 'z', find its first and last positions, and count the unique characters between them. This gives us all possible unique palindromic subsequences in an efficient manner.

The beauty of this approach is that it automatically handles the uniqueness requirement - by counting unique characters in the middle, we ensure each palindrome is counted exactly once, regardless of how many ways it can be formed.

Learn more about Prefix Sum patterns.

Solution Approach

The implementation follows a straightforward approach based on our intuition:

1. Enumerate all possible end characters: Since we're working with lowercase letters only, we iterate through all 26 letters from 'a' to 'z'. Each letter represents a potential pair of bookend characters for our palindromes.

2. Find first and last occurrences: For each character c, we use:

   • s.find(c) to get the first occurrence position l
   • s.rfind(c) to get the last occurrence position r

   If find() returns -1, it means the character doesn't exist in the string. If both l and r are the same, it means the character appears only once.

3. Check if valid palindrome can be formed: We verify that r - l > 1, which ensures there's at least one character between the first and last occurrence of c. This is necessary because we need a middle character to form a length-3 palindrome.

4. Count unique middle characters: If the condition is satisfied, we extract the substring between positions l+1 and r (exclusive) using s[l + 1 : r]. We then convert this substring to a set to get only unique characters. The size of this set represents the number of unique palindromes we can form with c as the bookend character.

5. Accumulate the result: We add the count of unique middle characters to our running total ans.

Here's how the algorithm works step by step:

ans = 0
for c in ascii_lowercase:  # Iterate 'a' to 'z'
    l, r = s.find(c), s.rfind(c)  # Find first and last positions
    if r - l > 1:  # At least one character between them
        ans += len(set(s[l + 1 : r]))  # Count unique chars in between
return ans

Time Complexity: O(26 * n) = O(n), where n is the length of the string. We iterate through 26 characters, and for each character, the find operations and set creation are O(n) in the worst case.

Space Complexity: O(1) for the algorithm itself (not counting the input), as we only use a constant amount of extra space. The set created for counting unique characters has at most 26 elements.

Example Walkthrough

Let's walk through the solution with the example string s = "aabca".

We'll iterate through each letter from 'a' to 'z' and check if it can form palindromes:

Character 'a':

• First occurrence: s.find('a') = 0
• Last occurrence: s.rfind('a') = 4
• Check if r - l > 1: 4 - 0 = 4 > 1 ✓ (valid)
• Extract substring between positions: s[1:4] = "abc"
• Unique characters in "abc": {'a', 'b', 'c'} (3 unique chars)
• Add 3 to our answer
• Possible palindromes: "aaa", "aba", "aca"

Character 'b':

• First occurrence: s.find('b') = 2
• Last occurrence: s.rfind('b') = 2
• Check if r - l > 1: 2 - 2 = 0 > 1 ✗ (not valid)
• Skip this character (appears only once)

Character 'c':

• First occurrence: s.find('c') = 3
• Last occurrence: s.rfind('c') = 3
• Check if r - l > 1: 3 - 3 = 0 > 1 ✗ (not valid)
• Skip this character (appears only once)

Characters 'd' through 'z':

• s.find() returns -1 for each (not in string)
• Skip all these characters

Final Result:

• Total unique palindromic subsequences = 3
• These are: "aaa", "aba", "aca"

Note how the algorithm automatically handles uniqueness: even though "aaa" can be formed in multiple ways (positions [0,1,4] or [0,2,4]), we count it only once because we're counting unique middle characters, not combinations.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × |Σ|), where n is the length of the string s and |Σ| is the size of the character set. In this problem, |Σ| = 26 since we iterate through all lowercase ASCII letters.

• The outer loop iterates through all 26 lowercase letters: O(26)
• For each character c:
  • s.find(c) takes O(n) time in the worst case
  • s.rfind(c) takes O(n) time in the worst case
  • Creating set(s[l + 1 : r]) involves:
    • Slicing the string: O(r - l) which is O(n) in the worst case
    • Creating a set from the slice: O(r - l) which is O(n) in the worst case
• Overall: O(26 × n) = O(n × |Σ|)

Space Complexity: O(|Σ|) or O(1)

• The set created in set(s[l + 1 : r]) can contain at most 26 unique characters (all lowercase letters), so it uses O(26) = O(|Σ|) space
• The string slice s[l + 1 : r] creates a temporary string of size O(n) in the worst case, but this is temporary and doesn't affect the overall space complexity since we only store the set
• Since |Σ| = 26 is a constant, the space complexity can also be expressed as O(1)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Attempting to Generate All Subsequences

Many developers initially try to generate all possible subsequences of length 3 and check if each is a palindrome. This brute force approach has a time complexity of O(n³) and will result in Time Limit Exceeded for large inputs.

Wrong Approach:

def countPalindromicSubsequence(self, s: str) -> int:
    palindromes = set()
    n = len(s)
    # This generates all subsequences - O(n³) complexity!
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if s[i] == s[k]:  # Check if palindrome
                    palindromes.add(s[i] + s[j] + s[k])
    return len(palindromes)

Solution: Use the optimized approach that focuses on finding first and last occurrences of each character.

2. Forgetting to Check Distance Between First and Last Occurrence

A common mistake is to forget checking if there's at least one character between the first and last occurrence of a character.

Wrong Code:

for char in ascii_lowercase:
    first_index = s.find(char)
    last_index = s.rfind(char)
    # Missing the check for r - l > 1
    if first_index != -1 and last_index != -1:  # Wrong condition!
        unique_chars_between = set(s[first_index + 1 : last_index])
        total_count += len(unique_chars_between)

This incorrectly counts cases where a character appears only once (first_index == last_index), resulting in an empty set but still processing it.

Solution: Always check if last_index - first_index > 1 to ensure there's space for a middle character.

3. Incorrect Substring Slicing

Getting the substring boundaries wrong when extracting characters between first and last occurrences.

Wrong Code:

# Including the boundary characters incorrectly
unique_chars_between = set(s[first_index : last_index + 1])  # Wrong!
# or
unique_chars_between = set(s[first_index : last_index])  # Also wrong!

Solution: Use s[first_index + 1 : last_index] to correctly exclude the boundary characters and get only the middle characters.

4. Not Handling Non-Existent Characters Properly

When using find() and rfind(), forgetting that they return -1 for non-existent characters can lead to incorrect substring operations.

Wrong Code:

for char in ascii_lowercase:
    first_index = s.find(char)
    last_index = s.rfind(char)
    # This will process even when char doesn't exist (indices are -1)
    unique_chars_between = set(s[first_index + 1 : last_index])
    total_count += len(unique_chars_between)

When both indices are -1, s[0:-1] would give an unexpected substring.

Solution: The condition if last_index - first_index > 1 naturally handles this case since -1 - (-1) = 0, which is not greater than 1.

5. Using Character Counting Instead of Position Finding

Some might try to use character frequency counting, which doesn't give position information needed to find characters between occurrences.

Wrong Approach:

from collections import Counter
char_count = Counter(s)
for char in char_count:
    if char_count[char] >= 2:  # This doesn't tell us what's between them!
        # Can't determine middle characters from frequency alone

Solution: Use find() and rfind() to get actual positions, not just counts.