LeetCode 1930. Unique Length-3 Palindromic Subsequences

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int countPalindromicSubsequence(string s) {
        int n = s.size(), ans = 0;
        for (int i = 0; i < 26; ++i) {
            int l = 0, r = n - 1, mask = 0, cnt = 0;
            while (l < n && s[l] != 'a' + i) ++l;
            while (r >= l && s[r] != 'a' + i) --r;
            if (r - l <= 1) continue;
            while (++l < r) {
                int idx = s[l] - 'a';
                mask |= (1 << idx);
            }
            for (int i = 0; i < 26; ++i) {
                if (mask >> i & 1)
                    ++cnt;
            }
            ans += cnt;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int countPalindromicSubsequence(string s) {
        int n = s.size(), l[26] = {[0 ... 25] = n}, r[26] = {}, mask, ans = 0;
        for (int i = 0; i < n; ++i) {
            int idx = s[i] - 'a';
            l[idx] = min(l[idx], i);
            r[idx] = i;
        }
        for (int i = 0; i < 26; ++i) {
            mask = 0;
            for (int j = l[i] + 1; j < r[i]; ++j) {
                int idx = s[j] - 'a';
                mask |= (1 << idx);
            }
            ans += __builtin_popcount(mask);
        }
        return ans;
    }
};