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;
    }