<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>

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        """
            Two brute force ways of doing this is by finding all the subsequnces in the array. That would be using
            DFS recursion, We dont need to do that because we dont need ALL subsequences because the problem wanted
            only those of length 3. o(2^n)

            Now to find only subsequences of lenghth, we can have 3 for loops and they will give us the subsequnces.
            O(n^3)

            An observation for 3 len palindrome is that the middle character can be any character, doesn't really matter, 
            the other two on the sides just have to be the same. So We can have loop in the array, which will start from 1 to 
            len(nums)-1, and then have two pointers on either end checking if they are equal. And adding palindormes to a hashset.

            For every iteration of mid, we need to check if any char from a-z is present both in the left and the right. So
            the time complexity will be 26 x n.
            The way we will do this is keep a left set which we will keep adding the middle element as we move on. This will 
            represent the elements we have on the left. And also have a hashmap on the right. We need to have a hashmap because
            we will slowly decrease the number of elements in the hashmap and if the count becomes 0, then we will pop. We cant
            have the count with a set as we have on the left side.

        """
        left_seen = set()
        right_seen = Counter(s)
        palindromes = set() # set of (middle, outer)
        for mid in range(len(s)):
            right_seen[s[mid]] -= 1
            if right_seen[s[mid]] == 0:
                right_seen.pop(s[mid])
            
            for j in range(26):
                c = chr(ord('a') + j)
                if c in left_seen and c in right_seen:
                    palindromes.add((s[mid], c))
            left_seen.add(s[mid])
        return len(palindromes)

        
2651