第 378 场力扣周赛

找出出现至少三次的最长特殊子字符串 II

题目

输入长度为 \(n\) 的由小写字母组成的字符串 \(s\)。如果一个字符串仅由单一字符组成，则它被称为特殊字符串。输出在 \(s\) 中出现至少三次的最长特殊非空子字符串的长度，如果不存在则输出 \(-1\)。

数据范围：\(3\leq n\leq 5\times 10^{5}\)。

思路

可以直接想到二分答案，时间复杂度为 \(O(n\log{n})\)。不过该题有 \(O(n)\) 的做法，其实就是分类讨论。首先遍历一边数组，将数组按照字母分段，把对应的长度存到桶中。假设字符串 \(s\) 的最长特殊子字符串的长度为 \(m\)，则答案必定在 \([m-2,m]\) 范围内，枚举答案然后判断是否满足条件即可。当然还可以像灵神一样讨论得更细，但是不好理解。

回文串重新排列查询

题目

输入长度为偶数 \(n\) 的字符串 \(s\)，以及长度为 \(m\) 的二维数组 \(q\)，其中 \(q_{i}=[a_{i},b_{i},c_{i},d_{i}]\)。对于每个查询 \(i\)，可以将区间 \([a_{i},b_{i}]\) 和 \([c_{i},d_{i}]\) 中的字符重新排列，输出是否能让字符串 \(s\) 变为回文串。每个查询是独立的。

数据范围：\(2\leq n\leq 10^{5}\)，\(1\leq m\leq 10^{5}\)，\(0\leq a_{i}\leq b_{i}<\frac{n}{2}\)，\(\frac{n}{2}\leq c_{i}\leq d_{i}<n\)。

思路

比赛时基本的思路是有的，就是没有实现出来。首先可以将后半段字符串反转，将原串当成两个字符串，这就将问题转化为判断操作之后两个字符串能否相等，从而简化实现。然后就是预处理前缀的字符计数（类似前缀和），最后对每个查询分类讨论，两个区间是相离、相交还是包含关系。个人觉得稍微复杂点的就是相交关系该如何判断，具体可以看题解区。