环绕字符串中唯一的子字符串 图解题解

这道题到底在问什么

输入

s = "zab"

输出

6 （z, a, b, za, ab, zab 都在环上连续）

输入

s = "cac"

输出

2 （只有 a 和 c 两个不同子串合法）

最优解：一步一步想明白

1. 3记住这套「是后继就 cur+1、否则归一，dp[当前字符]取较大值」，下面每一帧都在套它。最后把 dp 全部加起来就是答案。
2. 4先把 s 平铺出来。我们从左往右扫，维护两样东西:绿色高亮的「当前连续环绕段」，以及右侧 dp 面板「以每个字母结尾的最长段」。开扫。
3. 5开局看第 0 个字符 z。它前面没有字符，自己就是一段长度 1 的环绕段，cur = 1。
4. 6把它登记进 dp 面板:以字符 z 结尾的最长段目前是 1。dp[z] = 1。
5. 7扫到第 1 个字符 a，看它能不能接在前一个 z 后面。绿色那段是到上一个字符为止还在生长的环绕段，长度 1。
6. 8这里最妙:z 明明是字母表最后一个，但在环上它的下一个绕回 a。算式 (97 − 122 + 26) % 26 = 1，说明 a 正好是 z 的环绕后继，段能接着长。
7. 9a 接得上，绿色段延伸到长度 2。再看 dp[a]:之前是 0，现在 cur = 2，取较大值，dp[a] = 2。刷新了。
8. 10扫到第 2 个字符 b，看它能不能接在前一个 a 后面。绿色那段是到上一个字符为止还在生长的环绕段，长度 2。
9. 11b 接得上，绿色段延伸到长度 3。再看 dp[b]:之前是 0，现在 cur = 3，取较大值，dp[b] = 3。刷新了。
10. 12扫到第 3 个字符 a，看它能不能接在前一个 b 后面。绿色那段是到上一个字符为止还在生长的环绕段，长度 3。
11. 13注意 a 不是 b 的下一个（b 的下一个是 c）。算式结果不是 1，环绕段在这里断了。绿色段不能再往左连，cur 要归一，从第 3 个字符重新开始数。
12. 14a 接不上，绿色段缩回从第 3 个重新开始，cur = 1。dp[a] 之前是 2，和现在的 1 取较大值，结果 dp[a] = 2。原来的 2 更大,保留不动，这一步没白扫。
13. 15扫到第 4 个字符 b，看它能不能接在前一个 a 后面。绿色那段是到上一个字符为止还在生长的环绕段，长度 1。
14. 16b 接得上，绿色段延伸到长度 2。再看 dp[b]:之前是 3，现在 cur = 2，取较大值，dp[b] = 3。原值更大,保留不动。
15. 17扫到第 5 个字符 c，看它能不能接在前一个 b 后面。绿色那段是到上一个字符为止还在生长的环绕段，长度 2。
16. 18c 接得上，绿色段延伸到长度 3。再看 dp[c]:之前是 0，现在 cur = 3，取较大值，dp[c] = 3。刷新了。
17. 19整条字符串扫完了。dp 面板里每个字母对应「以它结尾的最长环绕段」，这些段互不相同（结尾字母不同就一定不同子串），所以直接把这些长度加起来，就是不同合法子串的总数。
18. 20加上 dp[z] = 1（以 z 结尾最长 1 个段，对应 1 个不同子串），当前累计 1。
19. 21加上 dp[a] = 2（以 a 结尾最长 2 个段，对应 2 个不同子串），当前累计 3。
20. 22加上 dp[b] = 3（以 b 结尾最长 3 个段，对应 3 个不同子串），当前累计 6。
21. 23加上 dp[c] = 3（以 c 结尾最长 3 个段，对应 3 个不同子串），当前累计 9。
22. 24把 dp[z]=1、dp[a]=2、dp[b]=3、dp[c]=3 全部相加，得到 9。这就是 s = "zababc" 中在环绕串里连续出现的不同子串个数,答案 9。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def findSubstringInWraproundString(self, s: str) -> int:
        f = defaultdict(int)
        k = 0
        for i, c in enumerate(s):
            if i and (ord(c) - ord(s[i - 1])) % 26 == 1:
                k += 1
            else:
                k = 1
            f[c] = max(f[c], k)
        return sum(f.values())

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int findSubstringInWraproundString(string s) {
        int f[26]{};
        int n = s.length();
        for (int i = 0, k = 0; i < n; ++i) {
            if (i && (s[i] - s[i - 1] + 26) % 26 == 1) {
                ++k;
            } else {
                k = 1;
            }
            f[s[i] - 'a'] = max(f[s[i] - 'a'], k);
        }
        return accumulate(begin(f), end(f), 0);
    }
};

import java.util.*;
class Solution {
    public int findSubstringInWraproundString(String s) {
        int[] f = new int[26];
        int n = s.length();
        for (int i = 0, k = 0; i < n; ++i) {
            if (i > 0 && (s.charAt(i) - s.charAt(i - 1) + 26) % 26 == 1) {
                ++k;
            } else {
                k = 1;
            }
            f[s.charAt(i) - 'a'] = Math.max(f[s.charAt(i) - 'a'], k);
        }
        return Arrays.stream(f).sum();
    }
}

复杂度

面试官可能追问