leetcode467. Unique Substrings in Wraparound String

题目要求

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-z26个字母无限循环的字符串s，现在输入一个字符串p，问该字符串有多少个子字符串在s中循环出现？

思路和代码

已知s是由一系列有序的从a-z的字母循环构成的字符串，因此可知，任何一个在s中循环出现的字符串，一定是遵循a-z-a这样的一个顺序规律的。因此，假如在p中相邻两个字符并非连续的，则这两个字符一定不会是循环出现。如cac这个例子，因为ca和ac并非连续，因此这两个字母一定不会构成循环子字符串。

接着就是如何去减少重复计算的场景。假设现在开始遍历以p[i]为结尾有多少循环的子字符串。如果p[i]和p[i-1]并非连续，则最多有1个循环的子字符串。如果p[i]和p[i-1]连续，并且已知以p[i-1]结尾的循环子字符串有count[i-1]个，则count[i] = count[i-1] + 1

但是问题到这时并未结束，还存在一个去重的场景，如abcabc，如果按照上述的方法计算，则会被计算出12个子字符串，但是实际上因为abc重复出现，所以只有6个循环子字符串。此处去重的方法为始终保留以每个字符作为结尾的最长子字符串长度。这里使用int[26] maxSubstring的数组来保留这个值。用上述方法计算出count[i]后，需要和maxSubstring[p[i]-‘a’]进行比较，假如长度不超过最长子字符串，则代表当前以该字符为结尾的所有情况都已经被考虑在内。否则需要将子字符串总量加上二者的差。

    public int findSubstringInWraproundString(String p) {
        int[] preMaxSubstring = new int[26];
        int prevLength = 0;
        int count = 0;
        for(int i = 0 ; i<p.length() ; i++) {
            char c = p.charAt(i);
            if(i == 0) {
                count++;
                preMaxSubstring[c-'a']++;
                prevLength++;
            }else {
                char prev = p.charAt(i-1);
                prevLength = (prev-'a'+1) % 26 == (c-'a') ? prevLength+1 : 1;
                if(prevLength > preMaxSubstring[c-'a']) {
                    count += prevLength - preMaxSubstring[c-'a'];
                    preMaxSubstring[c-'a'] = prevLength;
                }
            }
        }
        return count;
    }