> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/oj-practices/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/oj-practices/chapter1/dynamic-programming/467-unique-substrings-in-wraparound-string.md).

# 467     Unique Substrings in Wraparound String

## 467. [Unique Substrings in Wraparound String](https://leetcode.com/problems/unique-substrings-in-wraparound-string/description/)

## 1. Question

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.
```

## 2. Implementation

**(1) DP**

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

```java
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)