给定一个字符串s,s中只包含数字,请返回s中最长的特殊的回文子串的长度 特殊的回文子串t满足 ·t进行任何次交换后可以变成一个回文字符申 输入格式 输入第一行包含一个字符串s。 数据范围 1s≤10^5 输出格式 特殊的回文子串的最长长度

思路：字符串中只包含数字，那么可行的特殊的回文子串就只有两种，一种是全是同一个数字，一种是只有一个数字出现了奇数次，其他数字都出现了偶数次。因此，我们可以统计每个数字出现的次数，并且记录出现奇数次的数字的个数，最后根据这两个信息来确定最长的特殊回文子串的长度。

具体实现时，由于字符串长度可能非常长，使用桶来统计每个数字出现的次数。同时使用一个计数器 cnt 统计出现奇数次的数字个数。最后，如果 cnt=0，则说明字符串中只有同一个数字，返回字符串长度即可；如果 cnt>1，则说明字符串中不可能存在特殊回文子串，返回 0；否则，字符串中存在特殊回文子串，子串的长度为字符串长度减去奇数数字出现次数减去最后一个奇数数字出现次数。

时间复杂度

统计数字出现次数需要遍历整个字符串，时间复杂度为 O(n)，而遍历一遍桶，时间复杂度最多为 O(10)，因此总时间复杂度为 O(n)。

C++ 代码

class Solution {
public:
int longestSpecialSubstr(string s) {
vector<int> cnt(10);
for (char c : s) {
++cnt[c - '0'];
}
int odd_cnt = 0;
for (int i : cnt) {
odd_cnt += i & 1;
}
if (odd_cnt == 0) {
return s.size();
} else if (odd_cnt > 1) {
return 0;
}
int n = s.size();
int len = n - odd_cnt;
for (int i = 0, j = n - 1; i < j; ) {
if (cnt[s[i] - '0'] % 2 == 0) {
++i;
--len;
} else if (cnt[s[j] - '0'] % 2 == 0) {
--j;
--len;
} else {
if (s[i] == s[j]) {
len -= 2;
} else {
--len;
}
++i;
--j;
}
}
return len;
}
};

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/longest-special-substring/solution/zui-chang-te-shu-hui-wen-zi-chuan-by-leet-tqhx/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。