Unique Substrings in Wraparound String

https://leetcode.com/problems/unique-substrings-in-wraparound-string/description/

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.

Thoughts

开始想f[i][j]让它表示p(i, j)是否是子字符串。发现给的结果有重复的。于是又用了个set来存储已有结果，这样时间复杂度是O(n^3)，TLE.

看到其他人答案发现它们用的状态转移方程是以26个字母基础，即f[a]表示p中以a为结尾的substr数目。观察到这个数目刚好与p中以a结尾最长连续的字串相等。Example "abcd", the max number of unique substring ends with 'd' is 4, apparently they are "abcd", "bcd", "cd" and "d".

因为从该长度依次减去一个字符即一个susbtr. 因此f[a]实际上存的是以a为结尾的最长连续substring是多少.

Code

class Solution {
    public int findSubstringInWraproundString(String p) {
        int n = p.length();
        int[] f = new int[26];

        int longestCont = 0;
        for (int i = 0; i < n; i++) {
            if (i > 0 && (p.charAt(i) == p.charAt(i - 1) + 1 || p.charAt(i - 1) == 'z' && p.charAt(i) == 'a')) {
                longestCont++;        
            } else {
                longestCont = 1;
            }    
            int index = p.charAt(i) - 'a';
            f[index] = Math.max(f[index], longestCont);
        }

        int sum = 0;
        for (int i = 0; i < 26; i++) {
            sum += f[i];
        } 

        return sum;
    }
}

Analysis

时间复杂度O(n).