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

``````class Solution {
public:
int findSubstringInWraproundString(string p) {
vector<int> cnt(26, 0);
int len = 0;
for (int i = 0; i < p.size(); ++i) {
if (i > 0 && (p[i] == p[i - 1] + 1 || p[i - 1] - p[i] == 25)) {
++len;
} else {
len = 1;
}
cnt[p[i] - 'a'] = max(cnt[p[i] - 'a'], len);
}
return accumulate(cnt.begin(), cnt.end(), 0);
}
};
``````

``````class Solution {
public:
int findSubstringInWraproundString(string p) {
vector<int> cnt(26, 0);
int res = 0, len = 0;
for (int i = 0; i < p.size(); ++i) {
int cur = p[i] - 'a';
if (i > 0 && p[i - 1] != (cur + 26 - 1) % 26 + 'a') len = 0;
if (++len > cnt[cur]) {
res += len - cnt[cur];
cnt[cur] = len;
}
}
return res;
}
};
``````

https://discuss.leetcode.com/topic/70654/c-concise-solution

https://discuss.leetcode.com/topic/70658/concise-java-solution-using-dp/2

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation