Problem Description

We have an infinite string base that consists of the alphabet "abcdefghijklmnopqrstuvwxyz" repeated infinitely. So base looks like: "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".

Given a string s, we need to find how many unique non-empty substrings of s can be found in the infinite string base.

For example, if s = "zab", the substrings are:

• Single characters: "z", "a", "b" - all present in base
• Two characters: "za", "ab" - both present in base (note that "za" appears when wrapping from 'z' to 'a')
• Three characters: "zab" - present in base

The key insight is that valid substrings in base must be consecutive letters in alphabetical order, with the special case that 'z' can be followed by 'a' (wrapping around).

The solution uses dynamic programming to track the longest valid substring ending with each character. For each character in s, if it follows the previous character in alphabetical order (or wraps from 'z' to 'a'), we extend the current consecutive sequence. Otherwise, we start a new sequence of length 1. We keep track of the maximum length substring ending with each letter to avoid counting duplicates.

The final answer is the sum of the maximum lengths for all distinct ending characters, as this represents all unique substrings that can be found in base.

Intuition

The key observation is that any valid substring in base must consist of consecutive letters in alphabetical order (with wrapping from 'z' to 'a'). This means we're looking for substrings where each character is exactly one position after the previous character in the alphabet.

Let's think about how to count unique substrings efficiently. If we have a valid consecutive sequence like "abc", it contains the substrings "a", "b", "c", "ab", "bc", and "abc". Notice that all substrings ending with 'c' are: "c", "bc", "abc" - exactly 3 substrings, which equals the length of the consecutive sequence ending at 'c'.

This leads to an important insight: instead of tracking all possible substrings, we can track the longest consecutive sequence ending with each letter. Why the longest? Because if we have "abc" somewhere and "bc" somewhere else, the longer sequence "abc" already accounts for all substrings that "bc" would contribute (both "bc" and "c").

For each character in the alphabet, we only need to remember the maximum length of a consecutive sequence ending with that character. This avoids counting duplicates - if we see 'c' multiple times in different contexts, we only count the substrings from the longest sequence ending with 'c'.

The algorithm naturally follows: as we scan through the string, we maintain the current consecutive sequence length k. When we see a character that continues the sequence (differs from the previous by 1 in the circular alphabet), we extend k. Otherwise, we start fresh with k = 1. We then update our record for the maximum sequence length ending with the current character.

The final count is the sum of all maximum lengths, as each maximum length for character c represents the number of unique substrings ending with c.

Solution Approach

We implement the solution using dynamic programming with a hash map to track the maximum length of consecutive sequences ending with each character.

Data Structure:

• We use a dictionary f (implemented as defaultdict(int)) where f[c] stores the maximum length of a consecutive substring ending with character c.
• A variable k tracks the current consecutive sequence length.

Algorithm Steps:

1. Initialize tracking variables:

   • Create f as a defaultdict to store maximum lengths for each character
   • Set k = 0 to track the current consecutive sequence length

2. Iterate through the string: For each character c at position i:

   • Check if it continues the sequence:
     • Calculate (ord(c) - ord(s[i - 1])) % 26
     • If this equals 1, the current character follows the previous one in the circular alphabet
     • For example: 'b' after 'a' gives (98 - 97) % 26 = 1
     • Special case: 'a' after 'z' gives (97 - 122) % 26 = 1
   • Update the consecutive length k:
     • If consecutive: increment k by 1
     • Otherwise: reset k to 1 (start a new sequence)
   • Update the maximum for this character:
     • Set f[c] = max(f[c], k)
     • This ensures we keep only the longest sequence ending with c

3. Calculate the result:

   • Return sum(f.values())
   • Each value in f represents the count of unique substrings ending with that character

Why this works:

• A consecutive sequence of length n ending with character c contributes exactly n unique substrings (all suffixes ending with c)
• By keeping only the maximum length for each character, we avoid counting duplicate substrings
• The modulo 26 operation handles the wraparound from 'z' to 'a' elegantly

Time Complexity: O(n) where n is the length of string s
Space Complexity: O(1) as the dictionary can have at most 26 entries

Example Walkthrough

Let's walk through the example s = "zabc" to illustrate the solution approach.

Initial Setup:

• f = {} (empty dictionary to track max lengths)
• k = 0 (current consecutive sequence length)

Step 1: Process 'z' (index 0)

• First character, so we start a new sequence
• k = 1
• f['z'] = 1
• State: f = {'z': 1}

Step 2: Process 'a' (index 1)

• Check if 'a' follows 'z': (ord('a') - ord('z')) % 26 = (97 - 122) % 26 = -25 % 26 = 1 ✓
• It's consecutive! So k = k + 1 = 2
• f['a'] = max(f.get('a', 0), 2) = 2
• State: f = {'z': 1, 'a': 2}
• This means we found substrings "a" and "za" ending with 'a'

Step 3: Process 'b' (index 2)

• Check if 'b' follows 'a': (ord('b') - ord('a')) % 26 = (98 - 97) % 26 = 1 ✓
• It's consecutive! So k = k + 1 = 3
• f['b'] = max(f.get('b', 0), 3) = 3
• State: f = {'z': 1, 'a': 2, 'b': 3}
• This means we found substrings "b", "ab", and "zab" ending with 'b'

Step 4: Process 'c' (index 3)

• Check if 'c' follows 'b': (ord('c') - ord('b')) % 26 = (99 - 98) % 26 = 1 ✓
• It's consecutive! So k = k + 1 = 4
• f['c'] = max(f.get('c', 0), 4) = 4
• Final state: f = {'z': 1, 'a': 2, 'b': 3, 'c': 4}
• This means we found substrings "c", "bc", "abc", and "zabc" ending with 'c'

Calculate Result:

• Sum all values: 1 + 2 + 3 + 4 = 10

Unique substrings found:

1. Ending with 'z': "z" (1 substring)
2. Ending with 'a': "a", "za" (2 substrings)
3. Ending with 'b': "b", "ab", "zab" (3 substrings)
4. Ending with 'c': "c", "bc", "abc", "zabc" (4 substrings)

Total: 10 unique substrings that exist in the infinite base string.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string s. The algorithm iterates through the string exactly once using a single for loop with enumerate, performing constant-time operations for each character (checking conditions, updating variables, and dictionary operations).

The space complexity is O(|Σ|), where Σ is the character set. In this case, since we're dealing with lowercase English letters, |Σ| = 26. The defaultdict f stores at most one entry for each unique character in the alphabet, regardless of the input string length. Therefore, the space used by the dictionary is bounded by the size of the alphabet rather than the input size.

Common Pitfalls

Pitfall 1: Incorrect Wraparound Check

Issue: A common mistake is incorrectly checking if characters are consecutive, especially for the wraparound case from 'z' to 'a'.

Incorrect approach:

# Wrong: This doesn't handle wraparound correctly
if ord(char) - ord(s[index - 1]) == 1:
    consecutive_length += 1

Why it fails: When transitioning from 'z' to 'a', ord('a') - ord('z') = -25, not 1. This would miss valid consecutive sequences like "zab".

Correct approach:

# Use modulo 26 to handle wraparound
if (ord(char) - ord(s[index - 1])) % 26 == 1:
    consecutive_length += 1

Pitfall 2: Not Tracking Maximum Length Per Character

Issue: Simply counting all substrings without tracking the maximum length for each ending character leads to counting duplicates.

Incorrect approach:

# Wrong: This counts duplicates
total_count = 0
for i in range(len(s)):
    if consecutive:
        consecutive_length += 1
    else:
        consecutive_length = 1
    total_count += consecutive_length  # Adds all substrings

Why it fails: If "abc" appears twice in the string, this would count "a", "ab", "abc" twice, leading to incorrect results.

Correct approach:

# Keep only the maximum length for each ending character
max_length_ending_with[char] = max(max_length_ending_with[char], consecutive_length)
# Then sum all maximum values
return sum(max_length_ending_with.values())

Pitfall 3: Starting Index Edge Case

Issue: Forgetting to handle the first character properly or checking index bounds incorrectly.

Incorrect approach:

# Wrong: Doesn't handle i=0 case
for i in range(len(s)):
    if (ord(s[i]) - ord(s[i-1])) % 26 == 1:  # Error when i=0
        consecutive_length += 1

Correct approach:

# Check index > 0 before comparing with previous character
for index, char in enumerate(s):
    if index > 0 and (ord(char) - ord(s[index - 1])) % 26 == 1:
        consecutive_length += 1
    else:
        consecutive_length = 1

Pitfall 4: Understanding What Constitutes a Valid Substring

Issue: Misunderstanding that only consecutively increasing alphabetical sequences (with wraparound) are valid in the infinite base string.

Example: The substring "ca" is NOT valid in base because 'c' doesn't immediately follow 'a' in the alphabet. Only patterns like "abc", "xyz", "zabc" are valid.

Key insight: A substring is valid if and only if each character follows the previous one in alphabetical order (considering 'z' wraps to 'a').