leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1930.cpp (1700B)

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