leetcode

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 };