1. 題目鏈接：467. 環繞字符串中唯一的子字符串
2. 題目描述：
定義字符串
base為一個"abcdefghijklmnopqrstuvwxyz"無限環繞的字符串，所以base看起來是這樣的：
"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".給你一個字符串
s，請你統計并返回s中有多少 不同****非空子串 也在base中出現。示例 1：
輸入：s = "a" 輸出：1 解釋：字符串 s 的子字符串 "a" 在 base 中出現。示例 2：
輸入：s = "cac" 輸出：2 解釋：字符串 s 有兩個子字符串 ("a", "c") 在 base 中出現。示例 3：
輸入：s = "zab" 輸出：6 解釋：字符串 s 有六個子字符串 ("z", "a", "b", "za", "ab", and "zab") 在 base 中出現。提示：
1 <= s.length <= 105- s 由小寫英文字母組成
3. 解法（動態規劃）：
3.1 算法思路：
1. 狀態表示：
dp[i]表示：以 i位置的元素為結尾的所有子串里面，有多少個在 base中出現過
2. 狀態轉移方程：
對于 dp[i]，我們可以根據子串的長度劃分為兩類：
- 子串的長度等于1：此時這一個字符會出現在
base中 - 子串的長度大于1：如果
i位置的字符和i-1位置上的字符組合后，出現在base中的話，那么dp[i-1]里面的所有子串后面填上一個s[i]依舊在base中出現，因此dp[i]=dp[i-1]
綜上，dp[i]=1+dp[i-1]，其中 dp[i-1]是否加上需要先做一下判斷
3. 初始化：
將表里面的值都初始化為1
4. 填表順序：
從左往右
5. 返回值：
這里不能直接返回 dp表里面的和，因為會又重復的結果。在返回之前，我們需要先去重：
- 相同字符結尾的
dp值，我們僅需要保留最大的即可，其余dp值對應的子串都可以在最大的里面找到 - 可以創建一個大小為26的數組，統計所有字符結尾的最大
dp值 - 最后返回數組中所有元素的和即可
3.2 C++算法代碼：
class Solution {
public:int findSubstringInWraproundString(string s) {// 獲取字符串長度int n = s.size();// 初始化動態規劃數組，dp[i]表示以第i個字符結尾的最長連續子串的長度vector<int> dp(n, 1);// 遍歷字符串，從第二個字符開始for (int i = 1; i < n; i++) {// 如果當前字符與前一個字符相差1或者當前字符是'z'且前一個字符是'a'，則說明可以組成連續子串if (s[i] - 1 == s[i - 1] || (s[i - 1] == 'z' && s[i] == 'a')) {// 更新dp數組dp[i] = dp[i - 1] + 1;}}// 初始化哈希數組，用于記錄每個字符作為子串末尾時的最大長度int hash[26] = {0};// 遍歷dp數組，更新哈希數組for (int i = 0; i < n; i++) {hash[s[i] - 'a'] = max(hash[s[i] - 'a'], dp[i]);}// 計算所有子串長度之和int sum = 0;for (auto x : hash) sum += x;return sum;}
};
