LeetCode 2414 - Length of the Longest Alphabetical Continuous Substring

The problem asks us to find the length of the longest substring in a given string s where the characters appear in consecutive alphabetical order. An alphabetical continuous substring means that every adjacent pair of characters differs by exactly one in the alphabet.

leetcodemediumstring

LeetCode Problem 2414

Difficulty: 🟡 Medium
Topics: String

Solution

Problem Understanding

The problem asks us to find the length of the longest substring in a given string s where the characters appear in consecutive alphabetical order.

An alphabetical continuous substring means that every adjacent pair of characters differs by exactly one in the alphabet. For example:

  • "abc" is valid because:

  • 'b' comes immediately after 'a'

  • 'c' comes immediately after 'b'

  • "cde" is also valid

  • "abd" is not valid because 'd' does not immediately follow 'b'

  • "za" is not valid because the alphabet does not wrap around

The input is a lowercase English string with length between 1 and 10^5. This constraint is important because it tells us that inefficient substring enumeration approaches may become too slow. A quadratic algorithm could require billions of operations in the worst case.

The expected output is a single integer representing the maximum length among all valid alphabetical continuous substrings.

A few important observations help clarify the problem:

  • Every single character is trivially a valid continuous substring of length 1
  • We only care about contiguous substrings, not subsequences
  • The alphabet must increase forward by exactly one character each step
  • The sequence does not wrap from 'z' to 'a'

Some edge cases that could cause mistakes include:

  • A string of length 1
  • A string where no adjacent characters are consecutive
  • A string where the entire input is already continuous
  • Multiple continuous segments separated by invalid transitions
  • Repeated characters like "aaabbb" which should break continuity

Approaches

Brute Force Approach

The brute force solution considers every possible substring and checks whether it forms an alphabetical continuous string.

For each starting index i, we can extend the substring one character at a time toward the right. For every substring s[i:j], we verify whether all adjacent characters differ by exactly 1.

For example, given "abcde":

  • Start at index 0

  • "a" is valid

  • "ab" is valid

  • "abc" is valid

  • "abcd" is valid

  • "abcde" is valid

  • Start at index 1

  • "b" is valid

  • "bc" is valid

  • and so on

This method is correct because it exhaustively checks every substring and keeps track of the longest valid one.

However, it is too slow for large inputs. A string of length n contains O(n^2) substrings, and validating each substring can take up to O(n) time. Even with optimizations, the runtime becomes impractical for n = 10^5.

Optimal Approach

The key observation is that we do not actually need to examine every substring independently.

A substring is alphabetical continuous if every adjacent pair satisfies:

ord(s[i]) - ord(s[i - 1]) == 1

This means we can scan the string once while maintaining the length of the current valid continuous segment.

At each position:

  • If the current character follows the previous character alphabetically, we extend the current streak
  • Otherwise, we reset the streak length to 1

We continuously track the maximum streak length seen so far.

This transforms the problem into a simple linear scan.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) to O(n³) O(1) Checks many substrings repeatedly
Optimal O(n) O(1) Single pass using consecutive character checks

Algorithm Walkthrough

Step 1: Initialize Tracking Variables

Create two variables:

  • current_length, representing the current continuous substring length
  • max_length, representing the best answer seen so far

Both start at 1 because any single character is valid.

Step 2: Traverse the String

Iterate through the string starting from index 1.

At each position, compare the current character with the previous one.

Step 3: Check Alphabetical Continuity

If:

ord(s[i]) - ord(s[i - 1]) == 1

then the current character continues the sequence, so increment current_length.

Otherwise, the continuity breaks, so reset current_length to 1.

Step 4: Update the Maximum

After processing each character, update:

max_length = max(max_length, current_length)

This ensures we always remember the longest valid segment encountered.

Step 5: Return the Result

After finishing the traversal, return max_length.

Why it works

The algorithm maintains an invariant:

  • current_length always stores the length of the longest valid continuous substring ending at the current index

Whenever consecutive characters differ by exactly one, extending the substring is valid. Otherwise, any longer substring ending at the current index becomes invalid, so resetting to 1 is correct.

Because every character is processed exactly once and every valid segment is considered during the scan, the algorithm correctly finds the global maximum.

Python Solution

class Solution:
    def longestContinuousSubstring(self, s: str) -> int:
        max_length = 1
        current_length = 1

        for i in range(1, len(s)):
            if ord(s[i]) - ord(s[i - 1]) == 1:
                current_length += 1
            else:
                current_length = 1

            max_length = max(max_length, current_length)

        return max_length

The implementation begins by initializing both max_length and current_length to 1. This works because every single character forms a valid continuous substring.

The loop starts at index 1 since each character must be compared with its predecessor.

The expression:

ord(s[i]) - ord(s[i - 1]) == 1

checks whether the current character immediately follows the previous character in the alphabet.

If the condition is true, the current sequence continues, so we increment current_length.

If the condition is false, the sequence breaks and we reset current_length back to 1.

After each update, we compare current_length with max_length to maintain the best answer found so far.

Finally, the function returns max_length.

Go Solution

func longestContinuousSubstring(s string) int {
    maxLength := 1
    currentLength := 1

    for i := 1; i < len(s); i++ {
        if s[i]-s[i-1] == 1 {
            currentLength++
        } else {
            currentLength = 1
        }

        if currentLength > maxLength {
            maxLength = currentLength
        }
    }

    return maxLength
}

The Go implementation follows the same logic as the Python version.

One notable difference is that Go strings are byte slices internally, so accessing s[i] directly returns a byte. Since all characters are lowercase English letters, byte arithmetic is perfectly safe here.

No additional memory allocation is needed, and integer overflow is not a concern because the maximum substring length is at most 10^5.

Worked Examples

Example 1

Input:

s = "abacaba"

Step-by-step Trace

Index Character Previous Character Consecutive? current_length max_length
0 a - - 1 1
1 b a Yes 2 2
2 a b No 1 2
3 c a No 1 2
4 a c No 1 2
5 b a Yes 2 2
6 a b No 1 2

Final answer:

2

The longest valid substring is "ab".

Example 2

Input:

s = "abcde"

Step-by-step Trace

Index Character Previous Character Consecutive? current_length max_length
0 a - - 1 1
1 b a Yes 2 2
2 c b Yes 3 3
3 d c Yes 4 4
4 e d Yes 5 5

Final answer:

5

The entire string is a valid alphabetical continuous substring.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each character is processed exactly once
Space O(1) Only a few integer variables are used

The algorithm performs a single left-to-right scan of the string. Each iteration does constant work, so the runtime grows linearly with the input size.

The memory usage remains constant regardless of input length because no auxiliary data structures are allocated.

Test Cases

solution = Solution()

assert solution.longestContinuousSubstring("abacaba") == 2  # Basic mixed example
assert solution.longestContinuousSubstring("abcde") == 5  # Entire string valid
assert solution.longestContinuousSubstring("a") == 1  # Single character
assert solution.longestContinuousSubstring("z") == 1  # Single character at alphabet end
assert solution.longestContinuousSubstring("aaaaa") == 1  # Repeated characters
assert solution.longestContinuousSubstring("abd") == 2  # Partial valid substring
assert solution.longestContinuousSubstring("xyz") == 3  # Continuous near alphabet end
assert solution.longestContinuousSubstring("azbcdef") == 5  # Valid sequence after interruption
assert solution.longestContinuousSubstring("abcefgh") == 4  # Multiple segments
assert solution.longestContinuousSubstring("mnopqrst") == 8  # Long valid substring
assert solution.longestContinuousSubstring("zyx") == 1  # Reverse order
assert solution.longestContinuousSubstring("abcdefghijklmnopqrstuvwxy") == 25  # Large continuous substring

Test Summary

Test Why
"abacaba" Validates mixed valid and invalid transitions
"abcde" Verifies entire string can be valid
"a" Smallest possible input
"z" Boundary alphabet character
"aaaaa" Repeated letters should reset continuity
"abd" Tests interruption in sequence
"xyz" Continuous substring near alphabet end
"azbcdef" Ensures reset and restart logic works
"abcefgh" Multiple valid segments
"mnopqrst" Long uninterrupted sequence
"zyx" Descending order should not count
Long alphabet substring Stress test for larger valid sequence

Edge Cases

One important edge case is a single-character string such as "a". Since every individual character is automatically a valid alphabetical continuous substring, the correct answer must be 1. Implementations that initialize counters incorrectly may accidentally return 0. This solution avoids that issue by initializing both tracking variables to 1.

Another important case is repeated characters like "aaaa". Consecutive alphabetical continuity requires a difference of exactly 1, not 0. Therefore, repeated characters must break the sequence. The implementation correctly resets current_length whenever the difference condition fails.

A third important case is descending or non-consecutive characters such as "zyx" or "acdf". Some implementations mistakenly check only whether characters differ, rather than whether they differ by exactly one in increasing alphabetical order. This solution specifically checks:

ord(s[i]) - ord(s[i - 1]) == 1

which guarantees only strictly increasing consecutive characters extend the sequence.

Another subtle edge case involves interruptions followed by a new valid sequence, such as "abxyzabc". The algorithm must correctly reset after invalid transitions and begin counting again. Since the implementation resets current_length to 1 whenever continuity breaks, it naturally handles multiple independent continuous segments correctly.