Length of the Longest Alphabetical Continuous Substring

Med

#2198Time: O(n^2), where n is the length of the string `s`. The two nested loops lead to a quadratic runtime. In the worst-case scenario (a string like 'abcde...'), for each starting position `i`, the inner loop runs `n-i` times.Space: O(1). We only use a constant amount of extra space for variables like `maxLength`, `currentLength`, and loop indices.

Data structures

String

Prompt

An alphabetical continuous string is a string consisting of consecutive letters in the alphabet. In other words, it is any substring of the string "abcdefghijklmnopqrstuvwxyz".

For example, "abc" is an alphabetical continuous string, while "acb" and "za" are not.

Given a string s consisting of lowercase letters only, return the length of the longest alphabetical continuous substring.

Example 1:

Input: s = "abacaba"
Output: 2
Explanation: There are 4 distinct continuous substrings: "a", "b", "c" and "ab".
"ab" is the longest continuous substring.

Example 2:

Input: s = "abcde"
Output: 5
Explanation: "abcde" is the longest continuous substring.

Constraints:

1 <= s.length <= 10⁵
s consists of only English lowercase letters.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves checking every possible substring to see if it is an alphabetical continuous string. We iterate through all possible starting points of a substring and, for each starting point, we extend the substring as long as the alphabetical continuous property holds. We keep track of the maximum length found.

Algorithm

Initialize maxLength to 0. If the string is not empty, initialize it to 1.
Iterate through the string with an index i from 0 to n-1, where n is the length of the string. This index i will be the starting point of a potential substring.
For each i, start an inner loop with index j from i + 1 to n-1.
Inside the inner loop, check if the character at j is alphabetically consecutive to the character at j-1 (i.e., s.charAt(j) == s.charAt(j - 1) + 1).
If they are consecutive, it means the current alphabetical substring is extended. Increment a currentLength counter.
If they are not consecutive, the sequence is broken. Break the inner loop.
After the inner loop finishes for a given i, update maxLength with the maximum of its current value and the currentLength found for the substring starting at i.
After the outer loop completes, return maxLength.

Walkthrough

The brute-force method systematically explores all substrings. It uses two nested loops. The outer loop selects a starting character for a substring. The inner loop then expands this substring one character at a time, checking if the alphabetical continuity is maintained. A variable currentLength tracks the length of the valid continuous substring starting at the position defined by the outer loop. Whenever a character breaks the sequence, the inner loop terminates. The global maxLength is updated with the currentLength if it's larger. This process repeats for every character in the string as a potential starting point.

1class Solution {2    public int longestContinuousSubstring(String s) {3        if (s == null || s.isEmpty()) {4            return 0;5        }6        int maxLength = 0;7        int n = s.length();8        for (int i = 0; i < n; i++) {9            // For each starting point i, we find the longest10            // continuous substring starting from here.11            int currentLength = 1;12            for (int j = i + 1; j < n; j++) {13                if (s.charAt(j) == s.charAt(j - 1) + 1) {14                    currentLength++;15                } else {16                    break;17                }18            }19            maxLength = Math.max(maxLength, currentLength);20        }21        return maxLength;22    }23}

Complexity

Time

O(n^2), where n is the length of the string `s`. The two nested loops lead to a quadratic runtime. In the worst-case scenario (a string like 'abcde...'), for each starting position `i`, the inner loop runs `n-i` times.

Space

O(1). We only use a constant amount of extra space for variables like `maxLength`, `currentLength`, and loop indices.

Trade-offs

Pros

Simple to understand and implement.
It is a straightforward translation of the problem statement into code.

Cons

Highly inefficient for large inputs due to its O(n^2) time complexity.
Likely to cause a 'Time Limit Exceeded' (TLE) error on competitive programming platforms for the given constraints.
Performs redundant computations. For example, in 'abcd', the check for 'bcd' is done independently after the check for 'abcd' has already processed those characters.

A more efficient solution can be achieved by iterating through the string just once. We can maintain a count of the current length of the alphabetical continuous substring. When the continuous sequence breaks, we update our overall maximum length and reset the current count.

Algorithm

Handle the edge case of a null or empty string by returning 0. Otherwise, any non-empty string has a longest continuous substring of at least length 1.
Initialize maxLength = 1 and currentLength = 1.
Iterate through the string with an index i from 1 to n-1 (where n is the string length).
In each iteration, compare the character s.charAt(i) with the previous character s.charAt(i-1).
If s.charAt(i) == s.charAt(i-1) + 1, the alphabetical sequence continues. Increment currentLength.
If the condition is false, the sequence is broken. Reset currentLength to 1, as the current character s.charAt(i) starts a new potential sequence.
After either incrementing or resetting currentLength, update maxLength = Math.max(maxLength, currentLength) to keep track of the longest sequence found so far.
After the loop finishes, return maxLength.

Walkthrough

This optimal approach uses a single pass over the string, which is a common technique for problems involving contiguous subarrays or substrings. We use a variable, currentLength, to track the length of the alphabetical continuous substring ending at the current position.

We iterate from the second character of the string. At each character, we check if it forms a continuous sequence with the preceding character. If s.charAt(i) is exactly one greater than s.charAt(i-1), we are extending the current sequence, so we increment currentLength. If not, the sequence is broken, and we must start a new one from the current character, so we reset currentLength to 1.

In every step of the loop, we compare the currentLength with a maxLength variable and update maxLength if currentLength is greater. This ensures that maxLength always holds the length of the longest continuous substring found so far.

1class Solution {2    public int longestContinuousSubstring(String s) {3        if (s == null || s.isEmpty()) {4            return 0;5        }6 7        int maxLength = 1;8        int currentLength = 1;9 10        for (int i = 1; i < s.length(); i++) {11            // Check if the current character is consecutive to the previous one12            if (s.charAt(i) == s.charAt(i - 1) + 1) {13                currentLength++;14            } else {15                // If the sequence is broken, reset the current length16                currentLength = 1;17            }18            // Update the maximum length found so far19            maxLength = Math.max(maxLength, currentLength);20        }21 22        return maxLength;23    }24}

Complexity

Time

O(n), where n is the length of the string `s`. We perform a single pass through the string, and each operation inside the loop takes constant time.

Space

O(1). We only use a few variables (`maxLength`, `currentLength`, and the loop index) to store state, regardless of the input string's size.

Trade-offs

Pros

Extremely efficient with a linear time complexity of O(n).
Optimal solution that passes for large constraints.
Uses constant extra space.
The logic is clean and easy to follow once the concept is understood.

Cons

May be slightly less intuitive for a beginner compared to the brute-force method, as it requires thinking about state (currentLength) that carries over through iterations.

Solutions

Solution

1class Solution { public int longestContinuousSubstring ( String s ) { int ans = 0 ; int i = 0 , j = 1 ; for (; j < s . length (); ++ j ) { ans = Math . max ( ans , j - i ); if ( s . charAt ( j ) - s . charAt ( j - 1 ) != 1 ) { i = j ; } } ans = Math . max ( ans , j - i ); return ans ; } }

1class Solution { public: int longestContinuousSubstring ( string s ) { int ans = 0 ; int i = 0 , j = 1 ; for (; j < s . size (); ++ j ) { ans = max ( ans , j - i ); if ( s [ j ] - s [ j - 1 ] != 1 ) { i = j ; } } ans = max ( ans , j - i ); return ans ; } };

1class Solution : def longestContinuousSubstring ( self , s : str ) -> int : ans = 0 i , j = 0 , 1 while j < len ( s ): ans = max ( ans , j - i ) if ord ( s [ j ]) - ord ( s [ j - 1 ]) != 1 : i = j j += 1 ans = max ( ans , j - i ) return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem