lc2484
前缀、后缀数组分别统计数字对的出现次数，枚举字符串中间字符
累加前后缀相同数字对的乘积，得到长度为5的回文子序列总数。
class Solution {
const long MOD = 1e9 + 7;
public:
int countPalindromes(string s) {
int suf[10]{}, suf2[10][10]{}, pre[10]{}, pre2[10][10]{};
for (int i = s.length() - 1; i >= 0; --i) {
char d = s[i] - '0';
for (int j = 0; j < 10; ++j)
suf2[d][j] += suf[j];
++suf[d]; //预处理后缀
}
long ans = 0L;
for (char d : s) {
d -= '0';
--suf[d];
for (int j = 0; j < 10; ++j)
suf2[d][j] -= suf[j]; // 撤销
for (int j = 0; j < 10; ++j)
for (int k = 0; k < 10; ++k)
ans += (long) pre2[j][k] * suf2[j][k]; // 枚举所有字符组合
for (int j = 0; j < 10; ++j)
pre2[d][j] += pre[j];
++pre[d];
}
return ans % MOD;
}
};
lc1930
unordered_map<char, pair<int, int>> hash;算起止
class Solution {
public:
int countPalindromicSubsequence(string s)
{
int n = s.size();
unordered_map<char, pair<int, int>> hash;
for (int i = 0; i < n; ++i)
{
if (!hash.count(s[i]))
hash[s[i]].first = i;
hash[s[i]].second = i;
}
int ret = 0;
for (auto& [ch, pos] : hash) {
int first = pos.first;
int last = pos.second;
if (last - first < 2) continue; // 中间没有字符，无法形成长度为3的回文
unordered_set<char> st;
for (int i = first + 1; i < last; ++i)
st.insert(s[i]);
ret += st.size();
}
return ret;
}
};
优化
一次遍历+维护前后缀+枚举中间+位运算
前缀后缀二进制标记字符存在性
枚举字符串中间字符作为回文中心
has[mid] |= pre & suf;
累加得到长度为3的回文子序列总数
for (int mask : has)
ans += popcount((uint32_t) mask);算法就是 一次遍历 不断维护
class Solution {
public:
int countPalindromicSubsequence(string s) {
int n = s.size();
// 统计 [1,n-1] 每个字母的个数
int suf_cnt[26]{};
int suf = 0;
for (int i = 1; i < n; i++) {
int ch = s[i] - 'a';
suf_cnt[ch]++;
suf |= 1 << ch; // 把 ch 记录到二进制数 suf 中，表示后缀有 ch
}
int pre = 0;
int has[26]{}; // has[mid] = 由 alpha 组成的二进制数
for (int i = 1; i < n - 1; i++) { // 枚举中间字母 mid
int mid = s[i] - 'a';
suf_cnt[mid]--;
// 撤销 mid 的计数，suf_cnt 剩下的就是后缀 [i+1,n-1] 每个字母的个数
if (suf_cnt[mid] == 0)
// 后缀 [i+1,n-1] 不包含 mid
suf ^= 1 << mid;
// 从 suf 中去掉 mid
pre |= 1 << (s[i - 1] - 'a');
// 把 s[i-1] 记录到二进制数 pre 中，表示前缀有 s[i-1]
has[mid] |= pre & suf;
// 计算 pre 和 suf 的交集，|= 表示把交集中的字母加到 has[mid] 中
}
int ans = 0;
for (int mask : has) {
ans += popcount((uint32_t) mask);
//每个字符 has一个的记录表
// mask 中的每个 1 对应着一个 alpha
}
return ans;
}
};
