0467. Unique Substrings in Wraparound String
============================================
题目信息
--------
:题号: 0467
:难度: Medium
:主题: 小写字符串、环绕字母表、连续子串、不同结果计数
:原题: `LeetCode 0467 `_
:重点: 无限串按 ``a..z`` 循环、``z`` 后可接 ``a``、只统计 ``p`` 的连续子串、相同文本只计一次
题目重述
--------
考虑无限环绕字符串:
.. code-block:: text
...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz...
给定只包含小写英文字母的字符串 ``p``,统计 ``p`` 的不同非空连续子串中,有多少个也出现在该无限字符串中。
``p.length`` 位于 ``[1, 10^5]``。合法子串中相邻字符必须按字母表后继关系前进,并允许 ``z`` 后接 ``a``。同一字符串即使在 ``p`` 中出现多次,也只能计数一次。
自建示例
--------
跨越 z 到 a 的边界:
.. code-block:: text
输入:p = "xyzab"
输出:15
解释:整个字符串按 x、y、z、a、b 连续环绕,所有 5×6/2 = 15 个连续子串都合法且互不相同。
没有长度大于一的合法子串:
.. code-block:: text
输入:p = "cac"
输出:2
解释:不同单字符子串为 a 和 c;相邻字符 ca、ac 都不符合环绕后继关系,因此只有 2 个结果。
记录每个结尾字母能达到的最长长度
--------------------------------
若当前位置与前一字符满足环绕后继关系,则以当前位置结尾的合法连续段长度加 1;否则从 1 重新开始。设某个字母 ``c`` 作为结尾时出现过的最大长度为 ``best[c]``,那么长度 ``1..best[c]`` 的后缀都以 ``c`` 结尾且合法,每个长度对应一个不同的字符串。
同一字母的短合法串可能在多个位置重复出现,但只取最大长度就已经包含所有更短前缀,因此答案是 26 个最大长度之和。
C++ 实现
--------
.. code-block:: cpp
class Solution {
public:
int findSubstringInWraproundString(std::string p) {
std::array best{};
int length = 0;
for (int i = 0; i < static_cast(p.size()); ++i) {
if (i > 0 &&
(p[i] - p[i - 1] + 26) % 26 == 1) {
++length;
} else {
length = 1;
}
int letter = p[i] - 'a';
best[letter] = std::max(best[letter], length);
}
return std::accumulate(best.begin(), best.end(), 0);
}
};
代码分析
--------
``length`` 表示当前合法段的最大后缀长度,只有满足 ``z -> a`` 或普通相邻后继时才延长。对每个结尾字母只保留最大值,消除了重复子串的重复计数;时间复杂度为 ``O(|p|)``,额外空间复杂度为 ``O(1)``。