<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 {
public:
    int countPalindromicSubsequence(string s) {
        int len = s.size();
        if (len < 3) {
            return 0;
        }
        map<char, int> freq_map;
        map<char, vector<int>> pos_map;
        for (int i = 0; i < len; i++) {
            if (freq_map.find(s[i]) == freq_map.end()) {
                freq_map[s[i]] = 1;
                pos_map[s[i]].push_back(i);
            } else {
                freq_map[s[i]]++;
                pos_map[s[i]].push_back(i);
            }
        }
        int cnt = 0;
        map<char, vector<int>>::iterator it = pos_map.begin();
        while (it != pos_map.end()) {
            if(freq_map[it->first] == 1){
                it++;
                continue;
            }
            map<char, vector<int>>::iterator it2 = pos_map.begin();
            while (it2 != pos_map.end()) {
                vector<int> pos_range = it->second;
                int pos_min = pos_range.front();
                int pos_max = pos_range.back();
                pos_range = it2->second;
                vector<int>::iterator pos_tracker = pos_range.begin();
                while(pos_tracker != pos_range.end()){
                    if(*pos_tracker > pos_min && *pos_tracker < pos_max){
                        cnt++;
                        break;
                    }
                    pos_tracker++;
                }
                it2++;
            }
            it++;
        }
        return cnt;
        // vector<string> sets_of_3;
        // string target = "..";
        // for (int i = 0; i < len; i++) {
        //     if(freq_map[s[i]] > 1){
        //         target[0] = s[i];
        //         for (int j = i + 1; j < len; j++) {
        //             target[1] = s[j];
        //             if (find(sets_of_3.begin(), sets_of_3.end(), target) ==
        //                 sets_of_3.end()) {
        //                 for (int k = j + 1; k < len; k++) {
        //                     if (s[k] == s[i]) {
        //                         sets_of_3.push_back(target);
        //                         break;
        //                     }
        //                 }
        //             }
        //         }
        //     }
        // }
        // int cnt = sets_of_3.size();
        // return cnt;
    }
};
57029