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 <= 105sconsists 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;
}
};
Input
s = "a"
Output
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;
};
Input
s = "a"
Output
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())
Input
s = "cac"
Output
2