# Unique Length-3 Palindromic Subsequences
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/unique-length-3-palindromic-subsequences)
Canonical: https://scaleengineer.com/dsa/problems/unique-length-3-palindromic-subsequences
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Hash Table, String
---
## Problem
Given a string `s`, return _the number of **unique palindromes of length three** that are a **subsequence** of_ `s`.

Note that even if there are multiple ways to obtain the same subsequence, it is still only counted **once**.

A **palindrome** is a string that reads the same forwards and backwards.

A **subsequence** of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

* For example, `"ace"` is a subsequence of `"abcde"`.

**Example 1:**

**Input:** s = "aabca"
**Output:** 3
**Explanation:** The 3 palindromic subsequences of length 3 are:
- "aba" (subsequence of "aabca")
- "aaa" (subsequence of "aabca")
- "aca" (subsequence of "aabca")

**Example 2:**

**Input:** s = "adc"
**Output:** 0
**Explanation:** There are no palindromic subsequences of length 3 in "adc".

**Example 3:**

**Input:** s = "bbcbaba"
**Output:** 4
**Explanation:** The 4 palindromic subsequences of length 3 are:
- "bbb" (subsequence of "bbcbaba")
- "bcb" (subsequence of "bbcbaba")
- "bab" (subsequence of "bbcbaba")
- "aba" (subsequence of "bbcbaba")

**Constraints:**

* `3 <= s.length <= 105`
* `s` consists of only lowercase English letters.

# Approaches
## Brute-Force with Triple Nested Loops
This approach exhaustively checks every possible subsequence of length three. It uses three nested loops to pick three characters from the string `s` at indices `i`, `j`, and `k` such that `i < j < k`. For each subsequence, it checks if it's a palindrome. A `HashSet` is used to store the unique palindromes found to avoid duplicates.
**Time:** O(N³), where N is the length of the string `s`. The three nested loops lead to a cubic number of iterations. · **Space:** O(1). The `HashSet` stores the unique palindromes. Since there are only 26 lowercase English letters, the maximum number of unique length-3 palindromes is 26 (for the outer character) * 26 (for the middle character) = 676. This is a constant number, so the space complexity is O(1).
**Pros:** Simple to understand and implement.
**Cons:** Extremely inefficient due to the cubic time complexity.; Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.
### Explanation
The algorithm iterates through all possible combinations of three indices `i`, `j`, and `k` from the string `s`.
The conditions `0 <= i < j < k < s.length()` ensure that we are forming a valid subsequence of length three.
For each triplet of indices, we check if the characters at the outer indices `i` and `k` are the same (`s.charAt(i) == s.charAt(k)`). If they are, we have found a palindromic subsequence.
The formed palindrome string, `s.charAt(i)s.charAt(j)s.charAt(k)`, is added to a `HashSet<String>`. The use of a set automatically handles the uniqueness requirement; duplicate palindromes will not be added.
Finally, the size of the set gives the total number of unique length-3 palindromic subsequences.
```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int countPalindromicSubsequence(String s) {
        int n = s.length();
        Set<String> uniquePalindromes = new HashSet<>();

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (s.charAt(i) == s.charAt(k)) {
                        uniquePalindromes.add("" + s.charAt(i) + s.charAt(j) + s.charAt(k));
                    }
                }
            }
        }
        return uniquePalindromes.size();
    }
}
```
### Algorithm
- Initialize an empty `HashSet<String>` named `uniquePalindromes`.
- Use three nested loops with indices `i`, `j`, `k` to iterate through all triplets where `0 <= i < j < k < s.length()`.
- Inside the innermost loop, check if `s.charAt(i)` is equal to `s.charAt(k)`.
- If they are equal, construct the palindrome string and add it to `uniquePalindromes`.
- Return the final size of the `uniquePalindromes` set.

## Fixing the Middle Character
A more optimized approach involves iterating through each character of the string and considering it as the middle character of a potential palindrome. For each middle character at index `j`, we need to find an outer character `c` that appears both in the prefix `s[0...j-1]` and the suffix `s[j+1...N-1]`. By finding the intersection of unique characters in the prefix and suffix, we can form palindromes.
**Time:** O(N²). The main loop runs N times. Inside the loop, constructing the `left` and `right` sets takes O(j) and O(N-j) time respectively, which sums to O(N). Thus, the total complexity is O(N * N). · **Space:** O(1). The sets `left`, `right`, and `result` all store a constant maximum number of elements (26 for character sets, 676 for the result set).
**Pros:** More efficient than the brute-force O(N³) approach.
**Cons:** Still too slow for the given constraints, likely resulting in TLE.; Involves repeated computation as sets for prefixes and suffixes are rebuilt in each iteration.
### Explanation
This method iterates through the string from index `j = 1` to `n-2`, treating `s.charAt(j)` as the middle element of a palindrome `c s.charAt(j) c`.
For each `j`, we need to determine the set of available characters for the outer positions. An outer character `c` is valid if it exists at least once in the substring before `j` (the prefix) and at least once in the substring after `j` (the suffix).
We can find the unique characters in the prefix `s.substring(0, j)` and store them in a set, say `leftChars`.
Similarly, we find unique characters in the suffix `s.substring(j + 1)` and store them in `rightChars`.
Then, we iterate through all 26 lowercase letters. If a letter `c` is present in both `leftChars` and `rightChars`, it means we can form the palindrome `c s.charAt(j) c`.
We use a `HashSet<String>` to store these unique palindromes to get the final count.
```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int countPalindromicSubsequence(String s) {
        int n = s.length();
        Set<String> result = new HashSet<>();

        for (int j = 1; j < n - 1; j++) {
            Set<Character> left = new HashSet<>();
            for (int i = 0; i < j; i++) {
                left.add(s.charAt(i));
            }

            Set<Character> right = new HashSet<>();
            for (int k = j + 1; k < n; k++) {
                right.add(s.charAt(k));
            }

            for (char c : left) {
                if (right.contains(c)) {
                    result.add("" + c + s.charAt(j) + c);
                }
            }
        }
        return result.size();
    }
}
```
### Algorithm
- Initialize an empty `HashSet<String>` named `result`.
- Iterate with an index `j` from `1` to `n-2` to fix the middle character `s.charAt(j)`.
- For each `j`, create two sets: `left` for unique characters in `s[0...j-1]` and `right` for unique characters in `s[j+1...n-1]`.
- Iterate through the characters in the `left` set.
- If a character `c` from `left` is also present in the `right` set, form the palindrome string `c + s.charAt(j) + c` and add it to `result`.
- Return the size of the `result` set.

## Counting Unique Middle Characters Between First and Last Occurrences
The most efficient approach focuses on the structure of a length-3 palindrome, `XYX`. Instead of iterating through indices, we can iterate through all possible outer characters `X` (from 'a' to 'z'). For each `X`, we find its first and last occurrences in the string `s`. If `X` appears at least twice, any unique character `Y` found in the substring between these first and last occurrences can form a valid palindrome `XYX`. By summing up the counts of these unique middle characters for each possible `X`, we get the total number of unique palindromes.
**Time:** O(N). The main loop runs a constant 26 times. Inside the loop, `indexOf` and `lastIndexOf` take O(N) time. Finding unique characters in the substring also takes O(N) in the worst case. The total time complexity is O(26 * N), which simplifies to O(N). · **Space:** O(1). In each iteration of the outer loop, a `HashSet` is used to store middle characters. Since there are only 26 possible lowercase letters, the size of this set is bounded by a constant. Therefore, the space complexity is O(1).
**Pros:** Highly efficient with linear time complexity.; Conceptually clean and directly maps to the problem's structure.; Passes all constraints with ease.
**Cons:** Slightly more complex than brute-force but the performance gain is massive.
### Explanation
The core idea is that for any unique palindrome `XYX`, `X` must appear at least twice in the string `s`.
We can iterate through each character `c` from 'a' to 'z', considering it as the potential outer character `X`.
For each character `c`, we find its first index (`firstIndex`) and last index (`lastIndex`) in the string `s`.
If `firstIndex` is -1 or `firstIndex` is the same as `lastIndex`, it means `c` appears less than twice, so it cannot form the outer boundary of a length-3 palindrome. We skip to the next character.
If `firstIndex < lastIndex`, we have a valid pair of outer characters. The middle character `Y` can be any character present in the substring between these two indices, i.e., `s.substring(firstIndex + 1, lastIndex)`.
To find the number of unique palindromes for this outer character `c`, we just need to count the number of unique characters in this middle substring. A `HashSet<Character>` or a boolean array of size 26 can be used for this.
We add this count of unique middle characters to our total result. The final sum across all 26 possible outer characters is the answer.
```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int countPalindromicSubsequence(String s) {
        int totalUniquePalindromes = 0;
        // Iterate through all possible outer characters ('a' through 'z')
        for (char c = 'a'; c <= 'z'; c++) {
            int firstIndex = s.indexOf(c);
            int lastIndex = s.lastIndexOf(c);

            // Check if the character exists and appears at least twice
            if (firstIndex != -1 && firstIndex < lastIndex) {
                // A gap of at least 1 is needed for the middle character
                if (lastIndex > firstIndex + 1) {
                    // Find unique characters in the substring between the first and last occurrence
                    Set<Character> middleChars = new HashSet<>();
                    for (int i = firstIndex + 1; i < lastIndex; i++) {
                        middleChars.add(s.charAt(i));
                    }
                    totalUniquePalindromes += middleChars.size();
                }
            }
        }
        return totalUniquePalindromes;
    }
}
```
### Algorithm
- Initialize a counter `totalUniquePalindromes` to 0.
- Loop through each character `c` from 'a' to 'z'.
- Inside the loop, find the index of the first occurrence of `c` (`firstIndex`) and the last occurrence of `c` (`lastIndex`) in the string `s`.
- If `c` exists in the string and `firstIndex < lastIndex`, proceed.
- Create a `HashSet<Character>` to store the unique characters in the substring `s.substring(firstIndex + 1, lastIndex)`.
- Iterate from `firstIndex + 1` to `lastIndex - 1` and add each character to the set.
- Add the size of the set to `totalUniquePalindromes`.
- After checking all 26 characters, return `totalUniquePalindromes`.

# Solutions
### CSharp

```csharp
public class Solution {
    public int CountPalindromicSubsequence(string s) {
        int ans = 0;
        for (char c = 'a'; c <= 'z'; ++c) {
            int l = s.IndexOf(c), r = s.LastIndexOf(c);
            HashSet < char > cs = new HashSet < char > ();
            for (int i = l + 1; i < r; ++i) {
                cs.Add(s[i]);
            }
            ans += cs.Count;
        }
        return ans;
    }
}
```

### Java

```java
class Solution {
public
  int countPalindromicSubsequence(String s) {
    int ans = 0;
    for (char c = 'a'; c <= 'z'; ++c) {
      int l = s.indexOf(c), r = s.lastIndexOf(c);
      Set<Character> cs = new HashSet<>();
      for (int i = l + 1; i < r; ++i) {
        cs.add(s.charAt(i));
      }
      ans += cs.size();
    }
    return ans;
  }
}

```

### JavaScript

```javascript
export function countPalindromicSubsequence ( s ) { const cnt = new Map (); const n = s . length ; let ans = 0 ; for ( let i = 0 ; i < n ; i ++ ) { const ch = s [ i ]; if ( cnt . has ( ch )) cnt . get ( ch )[ 1 ] = i ; else cnt . set ( ch , [ i , i ]); } for ( const [ _ , [ i , j ]] of cnt ) { if ( i !== j ) { ans += new Set ( s . slice ( i + 1 , j )). size ; } } return ans ; }
```

### CPP

```cpp
class Solution {
public:
  int countPalindromicSubsequence(string s) {
    int ans = 0;
    for (char c = 'a'; c <= 'z'; ++c) {
      int l = s.find_first_of(c), r = s.find_last_of(c);
      unordered_set<char> cs;
      for (int i = l + 1; i < r; ++i)
        cs.insert(s[i]);
      ans += cs.size();
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def countPalindromicSubsequence(self, s: str) -> int: ans = 0 for c in ascii_lowercase: l, r = s . find(c), s . rfind(c) if r - l > 1: ans += len(set(s[l + 1: r])) return ans

```