建站工具的优点,调用wordpress数据库连接,wordpress 详情页,电子商务平台 网站 建设方式【LetMeFly】1542.找出最长的超赞子字符串#xff1a;前缀异或和#xff08;位运算#xff09;
力扣题目链接#xff1a;https://leetcode.cn/problems/find-longest-awesome-substring/
给你一个字符串 s 。请返回 s 中最长的 超赞子字符串 的长度。
「超赞子字符串」需…【LetMeFly】1542.找出最长的超赞子字符串前缀异或和位运算
力扣题目链接https://leetcode.cn/problems/find-longest-awesome-substring/
给你一个字符串 s 。请返回 s 中最长的 超赞子字符串 的长度。
「超赞子字符串」需满足满足下述两个条件
该字符串是 s 的一个非空子字符串进行任意次数的字符交换后该字符串可以变成一个回文字符串 示例 1
输入s 3242415
输出5
解释24241 是最长的超赞子字符串交换其中的字符后可以得到回文 24142示例 2
输入s 12345678
输出1示例 3
输入s 213123
输出6
解释213123 是最长的超赞子字符串交换其中的字符后可以得到回文 231132示例 4
输入s 00
输出2提示
1 s.length 10^5s 仅由数字组成
解题方法前缀和哈希表位运算
回文串有两种情况 所有字符都出现了偶数次、有且仅有一个字符出现了奇数次。 也就是说我们只用关心每个字符出现次数是奇数还是偶数即可。因此我们可以使用一个数 m a s k mask mask m a s k mask mask的第 i i i位表示数字 i i i出现次数是否为奇数次。 加入在 m a s k mask mask的基础上又出现了 i i i则新的 m a s k mask mask的计算公式为mask ^ 1 i。 我们只需要遍历一遍字符串并且使用哈希表哈希表 m a [ m a s k ] ma[mask] ma[mask]为前面所有数字结果为 m a s k mask mask的第一次出现位置。则遍历过程中有“ 若当前 m a s k mask mask出现过则这两次出现位置之间所有字符都出现了偶数次满足回文串要求若当前 m a s k mask mask变化一位后在哈希表中存在则这两次出现位置之间的字符串只有一个出现了奇数次满足回文串要求。 遍历结束算法结束。
时间复杂度 O ( l e n ( s ) × C ) O(len(s)\times C) O(len(s)×C)其中 C C C是字符个数这里 C 10 C10 C10空间复杂度 O ( min { l e n ( s ) , 2 C } ) O(\min\{len(s), 2^C\}) O(min{len(s),2C})
AC代码
C
class Solution {
public:int longestAwesome(string s) {int mask 0, ans 1;unordered_mapint, int ma;ma[0] -1;for (int i 0; i s.size(); i) {mask ^ (1 (s[i] - 0));if (ma.count(mask)) {ans max(ans, i - ma[mask]);}else {ma[mask] i;}// 一个奇数次字符for (int j 0; j 10; j) {int mask2 mask ^ (1 j);if (ma.count(mask2)) {ans max(ans, i - ma[mask2]);}}}return ans;}
};Python
class Solution:def longestAwesome(self, s: str) - int:mask, ans 0, 1ma {0: -1}for i in range(len(s)):mask ^ 1 (ord(s[i]) - ord(0))if mask in ma:ans max(ans, i - ma[mask])else:ma[mask] ifor j in range(10):mask2 mask ^ (1 j)if mask2 in ma:ans max(ans, i - ma[mask2])return ans同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/139077950
