Python 0467.py
class Solution:
def findSubstringInWraproundString(self, s: str) -> int:
result = 0
last = [ 0 ] * 26 # longest substring ending with that letter
expect = -1 # random number outside 0...25
length = 0
for c in s:
# map "a"..."z" to 0...25
c = ord(c) - ord("a")
# continue or reset
if c == expect:
length += 1
else:
length = 1
# next letter in alphabet incl. wraparound
expect = c + 1
if expect == 26: # same as mod 26
expect = 0
# even longer than before ?
last[c] = max(last[c], length)
return sum(last)
Difficulty
and has an acceptance rate of about 44% (100k+ submissions).
Typical patterns to solve this problem:
- Dynamic Programming
- String
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The implementation computes the number of distinct non-empty substrings of a given string s that appear in an infinite wrap-around alphabet string “…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz…”. It does so by scanning the input once, tracking the longest valid wrap-around substring that ends with each alphabet letter, and finally summing those lengths. The result equals the count of unique substrings because any shorter substring ending with the same letter is already covered by the longest one.
Core Logic
The algorithm maintains three mutable pieces of state while iterating over s:
length- length of the current contiguous wrap-around segment.expect- the alphabet index that is expected next for the segment to continue.last- a fixed-size array (26 entries) wherelast[i]stores the maximum length of a valid segment that ends with the character whose index isi.
At the end of the loop the sum of all entries in last yields the answer.
Mapping Characters
Each character from the input is converted to an integer in the range 0-25:
c = ord(c) - ord("a")
This numeric representation enables direct indexing into the last array and simplifies the wrap-around arithmetic.
Length Tracking
For every character the algorithm decides whether the current segment can be extended:
if c == expect:
length += 1
else:
length = 1
If the character matches the expected next letter, the segment grows; otherwise a new segment starts with length 1.
Updating Expected Character
After processing a character, the next expected alphabet index is prepared, taking the wrap-around from z to a into account:
expect = c + 1
if expect == 26:
expect = 0
This ensures that after a 'z' the algorithm correctly anticipates an 'a'.
Maintaining Max Length per Letter
The array entry for the current character is updated only when the newly observed segment is longer than any previously recorded one:
last[c] = max(last[c], length)
Because any substring ending with the same letter and shorter than the stored maximum is already represented, this single value per letter suffices to capture all distinct substrings.
Final Aggregation
When the loop finishes, the answer is obtained by summing the 26 entries:
return sum(last)
Each entry contributes exactly the count of unique substrings that terminate with its corresponding letter.
Edge Cases Handled
- Empty input - The loop body is never executed,
lastremains all zeros, and the sum correctly returns 0, representing no substrings. - Single-character strings - The first character triggers
lengthto become 1,lastreceives a value of 1 for that letter, and the final sum yields 1, the only possible substring. - Wrap-around transition - When the current character is
'z'(index 25) the calculation ofexpectwraps to 0, allowing an'a'to continue the segment seamlessly. - Non-consecutive letters - Any break in the alphabetical order resets
lengthto 1, ensuring that only valid wrap-around substrings contribute to the counts. - Repeated characters - Consecutive identical letters do not satisfy the
c == expectcondition, so each occurrence starts a new segment of length 1, correctly reflecting that substrings like"aa"are not part of the wrap-around alphabet.
Performance Optimizations
The solution achieves linear processing by iterating over the input string exactly once and performing only constant-time operations per character. The fixed-size array last eliminates the need for dynamic data structures, providing O(1) access and update. Using integer indices instead of character objects reduces overhead in comparisons and dictionary lookups. The final aggregation with sum(last) traverses a constant-size collection, adding negligible cost regardless of input length. These choices collectively keep the runtime tightly bound to the length of s while using minimal auxiliary memory.
ELI5 - Simplified Explanation
Imagine a very long train going around a circular track. The cars are labeled with letters from a to z. After the letter z, the train loops back around so that a comes right after z. This code watches the train pass by and keeps track of how long each string of cars is, as long as they are in the perfect alphabet order like a, b, c, d.
There are twenty-six cubbies in a row, with each one representing a different letter of the alphabet. Every time a letter appears, the code figures out how many car links it belongs to. If a letter appears again later in a much longer string of correct alphabet order, the code updates that letter’s cubby to remember the new, longer length.
Think of this like having a big treasure chest for every letter. If the code finds a string of length three ending in the letter c, it puts a three in the c cubby. If it later finds another string of length five that also ends in c, it replaces the three with a five because five is bigger. Once the whole train has passed, the code looks inside all twenty-six cubbies and adds up all the numbers inside them to see how many different strings were found.
Code Quality
Complexity Analysis
As a rule of thumb, the maximum input size for one second execution time is
- factorial: up to 10 elements
- exponential: up to 20 elements
- polynomial: a few thousand elements
- loglinear: up to 100,000 elements
- linear: a few million elements
- logarithmic: a billion elements
- constant: practically unlimited
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| author | solutions | |||||||||
| www | AlgoMonster | C++ | Python | Java | TS | |||||
| WalkCCC | C++ | Python | Java | |||||||
| leetcode.ca | C++ | Rust | Python | Java | Go | TS | ||||
| LeetcodeHelp | C++ | Python | Java | |||||||
| Progiez | C++ | Python | Java | |||||||
| github | black-shadows | C++ | ||||||||
| charles-wangkai | Java | |||||||||
| everthis | JS | |||||||||
| fengvyi | C++ | |||||||||
| fpdjsns | Python | |||||||||
| JoshCrozier | JS | |||||||||
| linouk23 | C++ | |||||||||
| lzl124631x | C++ | |||||||||
| ruoru | Rust | |||||||||
| suxrobGM | C# | |||||||||
| wisdompeak | C++ | |||||||||
| yuanliu666 | Kotlin | |||||||||
| AlgoMonster | C++, Python, Java, TypeScript | |||||||||
| WalkCCC | C++, Python, Java | |||||||||
| leetcode.ca | C++, Go, Java, Python, Rust, TypeScript | |||||||||
| LeetcodeHelp | C++, Java, Python | |||||||||
| Progiez | C++, Java, Python | |||||||||
| black-shadows | C++, C++ | |||||||||
| charles-wangkai | Java | |||||||||
| everthis | JavaScript | |||||||||
| fengvyi | C++ | |||||||||
| fpdjsns | Python | |||||||||
| JoshCrozier | JavaScript | |||||||||
| linouk23 | C++ | |||||||||
| lzl124631x | C++ | |||||||||
| ruoru | Rust | |||||||||
| suxrobGM | C# | |||||||||
| wisdompeak | C++ | |||||||||
| yuanliu666 | Kotlin |
Videos
Solved On The Same Day
- problem 481: Magical String
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality