467. Unique Substrings in Wraparound String ------M ~~~~~~

 Consider the string s to be the infinite wraparound string of "abcdefghijklmnopqrstuvwxyz", so s will look like this: "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".

Now we have another string p. Your job is to find out how many unique non-empty substrings of p are present in s. In particular, your input is the string p and you need to output the number of different non-empty substrings of p in the string s.

Note: p consists of only lowercase English letters and the size of p might be over 10000.

Example 1:

Input: "a"
Output: 1

Explanation: Only the substring "a" of string "a" is in the string s.

Example 2:

Input: "cac"
Output: 2
Explanation: There are two substrings "a", "c" of string "cac" in the string s.

Example 3:

Input: "zab"
Output: 6
Explanation: There are six substrings "z", "a", "b", "za", "ab", "zab" of string "zab" in the string s.

A:

首先，就是从每一个start index, 然后往后看，后面的是不是substring of s

class Solution {
public:
    int findSubstringInWraproundString(string p) {
        int n = p.length();
        unordered_set<string> mySet;
        for(int start =0; start <n; start++){// both start and end are inclusive 
            for(int end = start;end<n;end++){ // both start and end are inclusve                
                if(end == start || p[end] == p[end-1] +1 || ( p[end]=='a' && p[end-1] == 'z') ){
                    mySet.insert(p.substr(start,  end-start+1));
                }else{
                    break;
                }
            }
        }
        return mySet.size();
    }
};

然而LTE了

究其原因，如果p 是duplicated. 那么我们有太多重复计算的了。  （而且  len(p) > 10,000.  然而我们的字母只有26个）

很显然， 改进应该是在里面的这个for Loop

考虑这样的p   

"zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghifklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...".

这样就会每个都跑到最后去了

因此，我的idea是，对于每一个字母，例如'a', 找出其从他开始最长的串儿。

其长度，就是以 ‘a' 开始的字符串的数目

class Solution {
public:
    int findSubstringInWraproundString(string p) {
        int n = p.length();
        vector<int> maxLen(26,0);// maxLength of maxLen[ch-'a'] that it can reach
        for(int start =0; start <n; ){
            int end = start+1; // keep going untill we find non-fit position
            for(;end<n;end++){
                if( p[end] != p[end-1] +1 &&  not (p[end]=='a' && p[end-1] == 'z') ){
                    break;
                }
            }
            for(int i =start;i<min(end, start+26);i++){
                int index  = int(p[i]) - 'a';
                maxLen[index] = max(maxLen[index], end - i);
            }
            start = end;
        }
        return accumulate(maxLen.begin(), maxLen.end(), 0);
    }
};