<p>Given a string <code>s</code>, return <em>the number of <strong>unique palindromes of length three</strong> that are a <strong>subsequence</strong> of </em><code>s</code>.</p>

<p>Note that even if there are multiple ways to obtain the same subsequence, it is still only counted <strong>once</strong>.</p>

<p>A <strong>palindrome</strong> is a string that reads the same forwards and backwards.</p>

<p>A <strong>subsequence</strong> 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.</p>

<ul>
	<li>For example, <code>&quot;ace&quot;</code> is a subsequence of <code>&quot;<u>a</u>b<u>c</u>d<u>e</u>&quot;</code>.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aabca&quot;
<strong>Output:</strong> 3
<strong>Explanation:</strong> The 3 palindromic subsequences of length 3 are:
- &quot;aba&quot; (subsequence of &quot;<u>a</u>a<u>b</u>c<u>a</u>&quot;)
- &quot;aaa&quot; (subsequence of &quot;<u>aa</u>bc<u>a</u>&quot;)
- &quot;aca&quot; (subsequence of &quot;<u>a</u>ab<u>ca</u>&quot;)
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;adc&quot;
<strong>Output:</strong> 0
<strong>Explanation:</strong> There are no palindromic subsequences of length 3 in &quot;adc&quot;.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;bbcbaba&quot;
<strong>Output:</strong> 4
<strong>Explanation:</strong> The 4 palindromic subsequences of length 3 are:
- &quot;bbb&quot; (subsequence of &quot;<u>bb</u>c<u>b</u>aba&quot;)
- &quot;bcb&quot; (subsequence of &quot;<u>b</u>b<u>cb</u>aba&quot;)
- &quot;bab&quot; (subsequence of &quot;<u>b</u>bcb<u>ab</u>a&quot;)
- &quot;aba&quot; (subsequence of &quot;bbcb<u>aba</u>&quot;)
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>3 &lt;= s.length &lt;= 10<sup>5</sup></code></li>
	<li><code>s</code> consists of only lowercase English letters.</li>
</ul>

#The idea is that with a length-3 palindrome, the middle character doesn't matter at all, it can be anything, it will still be a palindrome IF the left and right char are the same! So our objective is to find unique answers of "left middle right" where left = right which can exist as subsequences. As we iterate through the string, we need a left set() to keep track of all the available chars on the left. The char that we are iterating will be treated as the middle char. Thus we will have a right dict that keeps track of the frequency of ALL elements. Then as we move along, we will remove/decrement the count of that particular element first. After which we can truly compare from 'a' to 'z', if any of these alphabets both exist inside left set and right dict. We do it this way because many ways can be found from subsequences, e.g. "abcdeba", if "c" was our middle, left at this point will have "a" and "b". Right dict will store all char as keys, value as count. So at this point the middle element "c" and all elements from its left will have its count decreased by then. But we know on the right there is still counts of "b" and "a" available. They can still form "a c a" or "b c b" palindromes. So this is why we iterate from a to z, and seeing if any alphabets exist in both left and right. Most imptly, the result is also a set, because we want unique palindromes only. At the end of this check, rmb to add the current element inside left set() since we are moving along to the right. At the end, return the length of result set.
# class Solution:
#     def countPalindromicSubsequence(self, s: str) -> int:
#         res = set() #keeps unique answers of (middle char, left/right char), at most 26^2 palindromes
#         left = set()
#         right = {}

#         for char in s:
#             right[char] = right.get(char, 0) + 1
        
#         for i in range(len(s)):
#             right[s[i]] -= 1
#             if right[s[i]] == 0:
#                 right.pop(s[i])
            
#             for j in range(26):
#                 char = chr(ord('a') + j) #Basically char becomes from 'a' to 'z'. Starting at j=0, ord('a') + j = ord('a'), chr(ord('a')) is just 'a'. Then chr(ord('a') + 1) is 'b', 'c'....'z'.
#                 if char in left and char in right:
#                     res.add((s[i], char))
            
#             left.add(s[i])
#         return len(res)
#Time: O(n), inner loop is fixed at 26 times, so 26n is still n
#Space: O(1), we do use sets and dict, BUT they are always constantly at 26 max, since lowercase alphabets only from a-z

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        res = set()  # Keeps unique answers of (middle char, left/right char)
        left = set()  # Tracks characters on the left side of the current character
        right = {}    # Tracks characters on the right side of the current character

        # Initialize the right dictionary with the frequency of each character
        for char in s:
            right[char] = right.get(char, 0) + 1

        # Iterate through the string
        for i in range(len(s)):
            right[s[i]] -= 1  # Decrement the count of the current character in the right dictionary
            if right[s[i]] == 0:
                right.pop(s[i])  # Remove the character from right if its count reaches zero

            # Iterate through characters in the left set (those encountered so far)
            for char in left:
                if char in right:  # Check if the character is also in the right dictionary
                    res.add((s[i], char))  # Add the tuple (middle char, left/right char) to the result set

            left.add(s[i])  # Add the current character to the left set

        return len(res)  # Return the size of the result set, which gives the number of unique palindromic subsequences

1355