<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:
        # need linear because of input size constraint
        # when we encouter a character that we have seen before, we can potentially form a palindromic subsequence
        # assuming that i >= 2 (0-indexed)
        # for a length 3 palindrome, we can fit any other character that exists in the middle.
        # how can we get all the other characters that occur after character? 
        # a clever solution entails considering each index as the middle character of three letter palindrome.
        # the thinking to get to this from the above solution is realizing that the structure of prefix sums can be leveraged here
        # the only way in a linear scan consider each character to be the end of the palindrome would entail keeping
        # track of the indices. and then in the worst case, it's possible that for a given charcter, we have to search for all
        # indices since it occurs many times
        # a variation would be to store some last index or some greatest or some idnex with some property
        # but i cannot think of such a solution without a counterexample
        # it was a good bservation intially that the the second letter really defines the palindrome
        # two passes then maybe? 
        # oh wait -- this might work because two passes can help you compute some variation of postfix information and prefix information
        # prefix choice + random char + postfix choice s.t. prefix choice == postfix choice is a three length palindrome!
        # and hten we can consider each index to be the random char and just search for what comes before and after.
        # but how can we pre-compute?
        left_set = set()
        right_map = Counter(s)
        res_set = set()
        for mid in s: 
            right_map[mid] -= 1
            if right_map[mid] == 0: 
                del right_map[mid]
            for i in range(26):
                c = chr(ord('a') + i)
                if c in left_set and c in right_map:
                    res_set.add((c, mid, c))
            left_set.add(mid)
        return len(res_set)
                    

                
2355