1930.cpp (1700B)
1 class Solution { 2 public: 3 int countPalindromicSubsequence(const string &s) const { 4 static pair<int, int> pos[27]; 5 memset(pos, 0xFF, sizeof(pos)); 6 7 const int n = s.size(); 8 for (int i = 0; i < n; i++) { 9 const int idx = s[i] & 0x1F; 10 if (pos[idx].first == -1) pos[idx].first = i; 11 pos[idx].second = i; 12 } 13 14 int res = 0; 15 for (int i = 1; i <= 26; i++) { 16 const auto [first, last] = pos[i]; 17 if (first == -1) continue; 18 bitset<27> bs; 19 for (int j = first + 1; j < last; j++) 20 bs.set(s[j] & 0x1F); 21 res += bs.count(); 22 } 23 return res; 24 } 25 }; 26 27 // Improve constant factor by using a lot of memory 28 class Solution { 29 public: 30 int countPalindromicSubsequence(const string &s) const { 31 static int count[100001][27]; 32 memset(count, 0x00, sizeof(int) * 27); 33 34 static pair<int, int> pos[27]; 35 memset(pos, 0xFF, sizeof(pos)); 36 37 const int n = s.size(); 38 for (int i = 0; i < n; i++) { 39 const int idx = s[i] & 0x1F; 40 if (i != 0) memcpy(count[i], count[i - 1], sizeof(int) * 27); 41 count[i][idx]++; 42 43 if (pos[idx].first == -1) pos[idx].first = i; 44 pos[idx].second = i; 45 } 46 47 int res = 0; 48 for (int i = 1; i <= 26; i++) { 49 const auto [first, last] = pos[i]; 50 if (first == -1) continue; 51 52 count[last][i]--; 53 for (int j = 1; j <= 26; j++) { 54 res += count[last][j] > count[first][j]; 55 } 56 count[last][i]++; 57 } 58 59 return res; 60 } 61 };