467 Unique Substrings in Wraparound String

467. Unique Substrings in Wraparound String

1. Question

Consider the stringsto be the infinite wraparound string of "abcdefghijklmnopqrstuvwxyz", soswill look like this: "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".

Now we have another stringp. Your job is to find out how many unique non-empty substrings ofpare present ins. In particular, your input is the stringpand you need to output the number of different non-empty substrings ofpin the strings.

Note:pconsists 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.

2. Implementation

(1) DP

思路: s是一个按照26个小写字母按照字典顺序排列的wraparound string，要在s中找出有多少个p的非空substring，我们只要在p中找出以每个character结尾的，符合条件的最长substring，注意这个长度本身就包含了以一个character结尾的，所有在s中出现的substring个数。dp[i]表示以character i (从a开始算)的最长substring

class Solution {
    public int findSubstringInWraproundString(String p) {
        if (p == null || p.length() == 0) {
            return 0;
        }

        int[] dp = new int[26];
        int maxLen = 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)) {
                ++maxLen;
            }
            else {
                maxLen = 1;
            }

            int index = p.charAt(i) - 'a';
            dp[index] = Math.max(maxLen, dp[index]);
        }

        int res = 0;
        for (int i = 0; i < 26; i++) {
            res += dp[i];
        }
        return res;
    }
}

3. Time & Space Complexity

时间复杂度O(n), n是p的长度，空间复杂度O(1)