<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:
        # # Brute force (TLE): check all subsequences of length 3, add 1 to count if they are palindromes.         
        # # O(n^3) i j k from 0 to n
        # n = len(s)
        # seen = set()
        # count = 0
        # for i in range(n - 2):
        #     for j in range(i + 1, n - 1):
        #         for k in range(i + 2, n):
        #             if not s[i] + s[j] in seen and s[i] == s[k]:
        #                 seen.add(s[i] + s[j])
        #                 count += 1
        # return count

        # Optimisation: O(n^2) we don't care about middle element
        n = len(s)
        seen = set()
        distinct_mids = {} # b : {b, c, a}
        res = 0
        for i in range(n - 2):
            if not s[i] in distinct_mids:
                distinct_mids[s[i]] = [[i, -1], set()]
            else:
                if i <= distinct_mids[s[i]][0][1]:
                    continue
            new_distincts = 0
            if i + 1 < n:
                if not s[i + 1] in distinct_mids[s[i]]:
                    distinct_mids[s[i]][1].add(s[i + 1])
                    new_distincts += 1
            for j in range(i + 2, n):
                if s[i] == s[j]:
                    # How many new distinct middle characters are seen
                    res += new_distincts
                    new_distincts = 0
                    distinct_mids[s[i]][0][1] = j
                if not s[j] in distinct_mids[s[i]][1]:
                    distinct_mids[s[i]][1].add(s[j])
                    new_distincts += 1
        return res
                    
                    
1392