Problem 467

Abstract / Summary

Count all unique substrings that can be formed from a string of consecutive letters in a circular alphabet.

Note

The full problem description, including helpful examples, can be found on LeetCode.

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)
24 lines | 762 bytes | submitted March 25, 2024 | GitHub   41% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 44% (100k+ submissions).

Typical patterns to solve this problem:
  • Dynamic Programming
  • String
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
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.
LeetCode profile | GitHub repo

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) where last[i] stores the maximum length of a valid segment that ends with the character whose index is i.

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, last remains all zeros, and the sum correctly returns 0, representing no substrings.
  • Single-character strings - The first character triggers length to become 1, last receives 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 of expect wraps to 0, allowing an 'a' to continue the segment seamlessly.
  • Non-consecutive letters - Any break in the alphabetical order resets length to 1, ensuring that only valid wrap-around substrings contribute to the counts.
  • Repeated characters - Consecutive identical letters do not satisfy the c == expect condition, 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.

written by openai gpt

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.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 26 | median = 8 | μ = 8.04 | σ = 0.98

Complexity Analysis

Time: linear
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
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
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
31 links | 17 authors | 9 languages

Videos

3 videos   did my crawler come up with invalid videos ? drop me a line.

Solved On The Same Day

1 medium
2 solutions   March 25, 2024

Extra

There are a few extra pages giving you some insights into my setup:
  • 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