[每日一题] 1542.找出最长的超赞子字符串

Richard

2024 年 05 月 20 日

121 次浏览

暂无评论

676字数

LeetCode

> https://leetcode.cn/problems/find-longest-awesome-substring/description/?envType=daily-question&envId=2024-05-06

为了满足超赞子字符串，字符串内的各字符数必须都是偶数，或仅有一个字符的个数为奇数。

因为字符串中仅含有数字，所以我们可以用 10 个二进制位来记录每个字符已经出现了奇数次还是偶数次，设为 `mask` 。因为 `mask` 是一个前缀和，所以想要知道每个子串中各字符的奇偶情况，只需要将子串中最后一个位置的 `mask` 和第一个位置的 `mask` 进行异或即可。

根据之前得出的超赞子字符串的判断条件，我们只需要找到和末尾位置具有相同或仅一位不同的 `mask` 即可。为了快速找到想要的 `mask` ，我们可以使用哈希表存下之前所有的 `mask` ，然后判断即可：

```c++
class Solution {
public:
    int longestAwesome(std::string s) {
        const int n = s.length();

std::unordered_map<int, int> prefix = {{0, -1}};
        int mask = 0, res = 0;
      
        for (int i = 0; i < n; i++) {
            mask ^= 1 << (s[i] - '0');
            if (prefix.find(mask) == prefix.end())
                prefix[mask] = i;
            else
                res = std::max(res, i - prefix[mask]);
          
            for (int offset = 0; offset < 10; offset++) {
                if (prefix.find(mask ^ (1 << offset)) != prefix.end())
                    res = std::max(res, i - prefix[mask ^ (1 << offset)]);
            }
        }

return res;
    }
};
```

- 时间复杂度：$O(n \times k)$ ，其中 $n$ 为字符串的长度； $k$ 为字符集的大小，本题中固定为 $10$ 。
- 空间复杂度：$O(min(n, 2^k))$ 。哈希表中每个键值对使用的空间为 $O(1)$ ，而键值对的数量由字符串的前缀串个数 $n + 1$ 和 `mask` 可能的取值范围 $2^k$ 决定，因此为 $O(min(n, 2^k))$ 。

最后修改：2024 年 05 月 20 日