leetcode1930 长度为 3 的不同回文子序列

思路1：

枚举中间的字符。具体实现中使用了位运算的技巧。

实现1：

 1 class Solution
 2 {
 3 public:
 4     int countPalindromicSubsequence(string s)
 5     {
 6         int n = s.length();
 7         vector<int> pre(n), suf(n);
 8         for (int i = 0; i < n; i++)
 9         {
10             int tmp = (i == 0 ? 0: pre[i - 1]);
11             pre[i] |= tmp; pre[i] |= 1 << s[i] - 'a';
12         }
13         for (int i = n - 1; i >= 0; i--)
14         {
15             int tmp = (i == n - 1 ? 0: suf[i + 1]);
16             suf[i] |= tmp; suf[i] |= 1 << s[i] - 'a';
17         }
18         vector<int> res(26, 0);
19         int ans = 0;
20         for (int i = 0; i < n; i++)
21         {
22             int P = (i == 0 ? 0: pre[i - 1]);
23             int S = (i == n - 1 ? 0: suf[i + 1]);
24             res[s[i] - 'a'] |= P & S;
25         }
26         for (int i = 0; i < 26; i++)
27         {
28             ans += __builtin_popcount(res[i]);
29         }
30         return ans;
31     }
32 };

思路2：

枚举两侧的字符。

实现2：

 1 class Solution
 2 {
 3 public:
 4     int countPalindromicSubsequence(string s)
 5     {
 6         int n = s.length();
 7         int ans = 0;
 8         for (int i = 0; i < 26; i++)
 9         {
10             int b = -1, e = -1;
11             for (int j = 0; j < n; j++)
12             {
13                 if (s[j] == char('a' + i))
14                 {
15                     if (b == -1) b = j;
16                     e = j;
17                 }
18             }
19             unordered_set<char> st;
20             if (b != -1)
21             {
22                 for (int i = b + 1; i < e; i++)
23                 {
24                     st.insert(s[i]);
25                 }
26             }
27             ans += (int)st.size();
28         }
29         return ans;
30     }
31 };