## Algorithm

Problem Name: 467. Unique Substrings in Wraparound String

We define the string `base` to be the infinite wraparound string of `"abcdefghijklmnopqrstuvwxyz"`, so `base` will look like this:

• `"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...."`.

Given a string `s`, return the number of unique non-empty substrings of `s` are present in `base`.

Example 1:

```Input: s = "a"
Output: 1
Explanation: Only the substring "a" of s is in base.
```

Example 2:

```Input: s = "cac"
Output: 2
Explanation: There are two substrings ("a", "c") of s in base.
```

Example 3:

```Input: s = "zab"
Output: 6
Explanation: There are six substrings ("z", "a", "b", "za", "ab", and "zab") of s in base.
```

Constraints:

• `1 <= s.length <= 105`
• `s` consists of lowercase English letters.

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
int findSubstringInWraproundString(string p) {
vector<int>dp(26);
int len = 0;
for(int i = 0; i  <  p.size(); i++){
len = (i > 0 && (p[i] - p[i - 1] == 1 || p[i] - p[i - 1] == -25)) ? len + 1 : 1;
dp[p[i] - 'a'] = max(dp[p[i] - 'a'], len);
}
int sum = 0;
for(int x: dp) sum += x;
return sum;
}
};
``````
Copy The Code &

Input

cmd
s = "a"

Output

cmd
1

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const findSubstringInWraproundString = function(p) {
// count[i] is the maximum unique substring end with ith letter.
// 0 - 'a', 1 - 'b', ..., 25 - 'z'.
const count = new Array(26).fill(0);

// store longest contiguous substring ends at current position.
let maxLengthCur = 0;

for (let i = 0; i  <  p.length; i++) {
if (i > 0
&& (p.charCodeAt(i) - p.charCodeAt(i - 1) === 1
|| (p.charCodeAt(i - 1) - p.charCodeAt(i) === 25))) {
maxLengthCur++;
}
else {
maxLengthCur = 1;
}

let index = p.charCodeAt(i) - ('a').charCodeAt(0);
count[index] = Math.max(count[index], maxLengthCur);
}

// Sum to get result
let sum = 0;
for (let i = 0; i  <  26; i++) {
sum += count[i];
}
return sum;
};
``````
Copy The Code &

Input

cmd
s = "a"

Output

cmd
1

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def findSubstringInWraproundString(self, p):
res, l = {i: 1 for i in p}, 1
for i, j in zip(p, p[1:]):
l = l + 1 if (ord(j) - ord(i)) % 26 == 1 else 1
res[j] = max(res[j], l)
return sum(res.values())
``````
Copy The Code &

Input

cmd
s = "cac"

Output

cmd
2