【每日一题】- 2020-09-15 - 467. 环绕字符串中唯一的子字符串

[azl397985856]

把字符串 s 看作是“abcdefghijklmnopqrstuvwxyz”的无限环绕字符串，所以 s 看起来是这样的："...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....". 

现在我们有了另一个字符串 p 。你需要的是找出 s 中有多少个唯一的 p 的非空子串，尤其是当你的输入是字符串 p ，你需要输出字符串 s 中 p 的不同的非空子串的数目。 

注意: p 仅由小写的英文字母组成，p 的大小可能超过 10000。

 

示例 1:

输入: "a"
输出: 1
解释: 字符串 S 中只有一个"a"子字符。
 

示例 2:

输入: "cac"
输出: 2
解释: 字符串 S 中的字符串“cac”只有两个子串“a”、“c”。.
 

示例 3:

输入: "zab"
输出: 6
解释: 在字符串 S 中有六个子串“z”、“a”、“b”、“za”、“ab”、“zab”。.
 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-substrings-in-wraparound-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[ZHAOXIN009]

C++ 题解;
只记录以独特字符结尾的子串的最大长度,所有26个字符结尾的字串的数量和就是最终结果.

执行用时：8 ms, 在所有 C++ 提交中击败了93.71%的用户
内存消耗：7.3 MB, 在所有 C++ 提交中击败了73.02%的用户

class Solution {
public:
    
    int findSubstringInWraproundString(string p) {
        vector<int>dp(26, 0);
        int sum=0;
        for(int i=0; i<p.size(); ++i){
            if(i>0 && (p[i]==p[i-1]+1||(p[i]=='a'&&p[i-1]=='z')) ){
                sum++;
            }
            else{
                sum=1;
            }
            dp[p[i]-'a']=max(dp[p[i]-'a'], sum);
        }
        return accumulate(dp.begin(), dp.end(), 0);
    }
};

[azl397985856]

思路

乍一看题目和最长上升子序列差不多， 但是：

1. 这道题有了首尾相连， 这难不倒我们
2. 这道题需要是连续的
3. 这道题相邻的两个数差值为 1，而最长上升子序列的差值是任意正整数（你可以把字母映射到 ascii code）

关于最长上升子序列 ，我写了一个专题，有兴趣的可以看下。 穿上衣服我就不认识你了？来聊聊最长上升子序列

也就是说这题根本不需要用到最长上升子序列的思路。

我刚开始的思路是能不能通过数学法来降维打击，想了想无果。 只能思考别的方法。

由于 p 的数据范围是 10^5 ，因此暴力找出所有子串就需要 10^10 次操作了，应该会超时。而且题目很多信息都没用到，肯定不对。

算法：

• 定义一个 len_mapper。key 是 字母， value 是 长度。 含义是以 key 结尾的最长连续子串的长度。

关键字是：最长

• 用一个变量 w 记录连续子串的长度，遍历过程根据 w 的值更新 len_mapper
• 返回 len_mapper 中所有 value 的和。

比如: abc，此时的 len_mapper 为:

{
 c: 3
 b: 2
 a: 1
}

比如：abcab，此时的len_mapper 依旧。

比如: abcazabc，此时的len_mapper：

{
 c: 4
 b: 3
 a: 2
 z: 1
}

这就得到了去重的目的。

这种算法是不重不漏的，因为最长的连续子串一定是包含了比它短的连续子串，这个思想和 1297. 子串的最大出现次数 剪枝的方法有异曲同工之妙。

代码（Python）

class Solution:
    def findSubstringInWraproundString(self, p: str) -> int:
        p = '^' + p
        len_mapper = collections.defaultdict(lambda: 0)
        w = 1
        for i in range(1,len(p)):
            if ord(p[i])-ord(p[i-1]) == 1 or ord(p[i])-ord(p[i-1]) == -25:
                w += 1
            else:
                w = 1
            len_mapper[p[i]] = max(len_mapper[p[i]], w)
        return sum(len_mapper.values())

复杂度分析

• 时间复杂度：$O(N)$,其中 N 为 P 的长度。
• 空间复杂度：$O(N)$,其中 N 为 P 的长度。

更多题解可以访问我的LeetCode题解仓库：https://github.com/azl397985856/leetcode 。 目前已经35K star啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

[stale]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.