Formatted question description: https://leetcode.ca/all/467.html
467. Unique Substrings in Wraparound String
Level
Medium
Description
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 nonempty substrings of p
are present in s
. In particular, your input is the string p
and you need to output the number of different nonempty 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.
Solution
If p
has length 0, return 0.
Use an array counts
with length 26 to store the number of unique substrings that ends with each letter. The first character in p
(or p.charAt(0)
) has an initial count of 1. Loop over p
and compare each pair of adjacent characters. If the two adjacent characters differ by 1 (the two adjacent characters are “ab”, “bc”, “cd”, …, “xy”, “yz”, “za”), then the latter character has a count which is the previous count plus 1 (here “count” means the number of unique substrings that ends with the character). Otherwise, the latter character has a count 1. Update the character’s count to maintain its maximum count.
Finally, for each letter, obtain the number of unique substrings that ends with the letter. Calculate the sum and return.

class Solution { public int findSubstringInWraproundString(String p) { if (p == null  p.length() == 0) return 0; int[] counts = new int[26]; int length = p.length(); counts[p.charAt(0)  'a'] = 1; int prevCount = 1; for (int i = 1; i < length; i++) { char curC = p.charAt(i), prevC = p.charAt(i  1); int curIndex = curC  'a', prevIndex = prevC  'a'; int dif = (curIndex  prevIndex + 26) % 26; int curCount = dif == 1 ? prevCount + 1 : 1; counts[curIndex] = Math.max(counts[curIndex], curCount); prevCount = curCount; } int sum = 0; for (int count : counts) sum += count; return sum; } }

Todo

class Solution(object): def findSubstringInWraproundString(self, p): """ :type p: str :rtype: int """ d = {} cnt = 0 for i in range(len(p)): if i > 0 and (ord(p[i])  ord(p[i  1]) == 1 or ord(p[i  1])  ord(p[i]) == 25): cnt += 1 else: cnt = 1 d[ord(p[i])] = max(d.get(ord(p[i]), 0), cnt) return sum(d.values())