Unique Substrings in Wraparound String
Medium · 1-D Dynamic Programming · Explanation and code example
Longest Wraparound Run per Ending Letter
How it works
A consecutive run can continue from z to a. For each ending letter, keep the longest valid run ending there. Every shorter suffix ending with that letter is determined uniquely, so adding these maxima counts distinct substrings without storing them.
Steps
- Extend the run when adjacent letters are consecutive, including z to a.
- Otherwise restart the run at one.
- Update the ending letter’s maximum and sum all 26 maxima.
Complexity
- Time: O(n).
- Space: O(26).
Things to watch for
- Include the z-to-a transition.
- Sum maxima per ending letter, rather than every encountered run length.
- Repeated occurrences must not count the same substring twice.
Python code example
class Solution:
def findSubstringInWraproundString(self, s: str) -> int:
maxLength = 1
# count[i] := the number of substrings ending in ('a' + i)
count = [0] * 26
for i in range(len(s)):
if i > 0 and (ord(s[i]) - ord(s[i - 1]) == 1
or ord(s[i - 1]) - ord(s[i]) == 25):
maxLength += 1
else:
maxLength = 1
index = ord(s[i]) - ord('a')
count[index] = max(count[index], maxLength)
return sum(count)
C++ code example
class Solution {
public:
int findSubstringInWraproundString(string s) {
int maxLength = 1;
// count[i] := the number of substrings ending in ('a' + i)
vector<int> count(26);
for (int i = 0; i < s.length(); ++i) {
if (i > 0 && (s[i] - s[i - 1] == 1 || s[i - 1] - s[i] == 25))
++maxLength;
else
maxLength = 1;
const int index = s[i] - 'a';
count[index] = max(count[index], maxLength);
}
return accumulate(count.begin(), count.end(), 0);
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.