467. 环绕字符串中唯一的子字符串 - 力扣LeetCode题目描述把字符串s看作无限环绕字符串...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....的一部分。 现在给定字符串s求s中有多少个唯一的非空子串这个子串在环绕串中出现。示例 输入: s zab 输出: 6 解释有 6 个唯一子串z、a、b、za、ab、zab思路分析核心观察合法子串必须是连续递增a→b→c...z→a。同一个结尾字母我们只需要保留最长连续子串的长度。举例以b结尾最长连续长度是 3那么它能贡献 3 个子串b、ab、zab短的可以直接忽略避免重复统计。状态定义dp[i]以 s [i] 结尾的最长连续环绕子串的长度初始化dp[i]1单个字符自身长度为 1转移条件 如果s[i-1]1 s[i]或者s[i-1]z s[i]a说明连续dp[i] dp[i-1] 1否则dp[i]保持 1断开。去重关键本题精华开数组ch[26]ch[c-a]保存以字符 c 结尾的最长连续子串长度。为什么取最大值 比如sabab两个b第一个 b 的 dp2第二个 b 的 dp2。以 b 结尾最长就是 2只贡献 2 个子串防止重复计数。最后把 ch 数组 26 个值全部累加就是答案。【去重例子】s abcdxyzabcd现在来了两段 abcdabcdxyzabcds a b c d x y z a b c d先看两段 d 第一段末尾 ddp4 第二段末尾 ddp 算出来是 7。 ch [d] max (4,7) → 取 7第一段 d 产生的子串d、cd、bcd、abcd第二段更长的以 d 结尾串包含上面全部还新增更多子串。 旧的那一组完全重复所以直接丢弃旧的 4保留最大值 7。ch [a]第一次 a dp1后面第二个 a dp4 → ch [a]max (1,4)4 ch [b]第一次 b dp2后面第二个 b dp5 → ch [b]max (2,5)5class Solution { public: int findSubstringInWraproundString(string s) { int n s.size(); vectorint dp(n,1); int ch[26]{0}; int ret 0; for (int i 1; i n; i) { if (s[i - 1] 1 s[i] || (s[i - 1] z s[i] a)) { dp[i] dp[i - 1]; } } for(int i0;in;i) { ch[s[i]-a]max(dp[i],ch[s[i]-a]); } for (auto e : ch) rete; return ret; } };