题目

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.

分析

已知有一个无限循环的字符串s: "abc...xyz"+"abc..xyz"...+...，给你一个字符串，问这个字符串有多少个子串在s中。
这道题开始想用两个指针做，但是会引起重复，比如cac中会得到c 和 ac 和c。
其实应该使用动态规划，代码很好写，思路不好想。
得到以每个字符结尾的最大合乎要求的长度，加起来就是最终结果
比如abcd以d结尾，长度为4，则有abcd,bcd,cd,d这四个子串，再加上以a、b、c结尾的，就是最终结果，而且取最长的可以避免重复。

The idea is, if we know the max number of unique substrings in p ends with 'a', 'b', ..., 'z', then the summary of them is the answer. Why is that?

1. The max number of unique substring ends with a letter equals to the length of max contiguous substring ends with that letter. Example "abcd", the max number of unique substring ends with 'd' is 4, apparently they are "abcd", "bcd", "cd" and "d".
2. If there are overlapping, we only need to consider the longest one because it covers all the possible substrings. Example: "abcdbcd", the max number of unique substring ends with 'd' is 4 and all substrings formed by the 2nd "bcd" part are covered in the 4 substrings already.
3. No matter how long is a contiguous substring in p, it is in s since s has infinite length.
4. Now we know the max number of unique substrings in p ends with 'a', 'b', ..., 'z' and those substrings are all in s. Summary is the answer, according to the question.

代码

public int findSubstringInWraproundString(String p) {
    // count[i] is the maximum unique substring end with ith letter.
    // 0 - 'a', 1 - 'b', ..., 25 - 'z'.
    int[] count = new int[26];
    
    // store longest contiguous substring ends at current position.
    int maxLengthCur = 0; 

    for (int i = 0; i < p.length(); i++) {
        if (i > 0 && (p.charAt(i) - p.charAt(i - 1) == 1 || (p.charAt(i - 1) - p.charAt(i) == 25))) {
            maxLengthCur++;
        }
        else {
            maxLengthCur = 1;
        }
        
        int index = p.charAt(i) - 'a';
        count[index] = Math.max(count[index], maxLengthCur);
    }
    
    // Sum to get result
    int sum = 0;
    for (int i = 0; i < 26; i++) {
        sum += count[i];
    }
    return sum;
}