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".
"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 <= 105s consists of only English lowercase letters.Problem Overview: You are given a lowercase string s. The task is to find the length of the longest substring where every character is exactly one letter after the previous one in the alphabet. For example, "abc" or "xyz" are valid because each character follows its predecessor by +1 in ASCII order.
Approach 1: Sliding Window (O(n) time, O(1) space)
This approach scans the string once while maintaining the length of the current alphabetical run. Start from the second character and compare it with the previous one. If s[i] - s[i-1] == 1, the sequence continues and you extend the window by increasing the current length. Otherwise, reset the window length to 1 because the alphabetical chain breaks. Track the maximum length seen during the traversal. The algorithm uses constant extra memory and performs a single linear pass, which makes it optimal. This technique is a classic pattern from sliding window problems and appears frequently in string traversal tasks.
Approach 2: Dynamic Programming (O(n) time, O(n) space)
The dynamic programming formulation treats each index as the end of a potential alphabetical substring. Define dp[i] as the length of the longest valid substring ending at index i. If s[i] - s[i-1] == 1, extend the previous result with dp[i] = dp[i-1] + 1. Otherwise start a new sequence with dp[i] = 1. After processing the entire string, the maximum value in the DP array is the answer. This mirrors the logic used in dynamic programming problems where each state depends on the previous one. While it is conceptually clear, it uses extra memory compared to the sliding window solution.
Recommended for interviews: The sliding window solution is what most interviewers expect. It demonstrates that you can recognize consecutive relationships and maintain a running window in O(n) time with O(1) space. Implementing the DP version first can help reason about the recurrence, but reducing it to a constant-space scan shows stronger algorithmic optimization skills.
The sliding window approach will help us identify the longest substring of consecutive characters. We iterate through the string, expanding the window by adding characters as long as they are consecutive. If characters are not consecutive, we reset the start of the window to the current character. We maintain a variable to track the maximum length found during this process.
This implementation uses a loop to iterate through the string and checks the difference between consecutive characters. When characters are consecutive, it increases the current length. If a break is found, it resets the current length to 1. The maximum length is updated whenever a longer continuous substring is found.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), since only a few constant space variables are used.
This approach uses an array to keep track of the longest continuous substring ending with each character of the input string. We initialize an array with ones. As we iterate through the string, we increment the array value if the current character forms a continuous sequence with the previous character, and we keep track of the maximum value in this array.
In this C implementation, an array dp stores the length of the longest substring ending at each character position, and updates the dp values by checking for sequential characters and tracking maximum length found.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), due to the additional array used for dynamic programming.
We can traverse the string s and use a variable ans to record the length of the longest lexicographically consecutive substring, and another variable cnt to record the length of the current consecutive substring. Initially, ans = cnt = 1.
Next, we start traversing the string s from the character at index 1. For each character s[i], if s[i] - s[i - 1] = 1, it means the current character and the previous character are consecutive. In this case, cnt = cnt + 1, and we update ans = max(ans, cnt). Otherwise, it means the current character and the previous character are not consecutive, so cnt = 1.
Finally, we return ans.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: O(n), where n is the length of the string. |
| Dynamic Programming Approach | Time Complexity: O(n), where n is the length of the string. |
| Single Pass | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window | O(n) | O(1) | Best general solution. One pass with constant memory. Preferred for interviews. |
| Dynamic Programming | O(n) | O(n) | Useful when explaining recurrence relations or when extending the problem to store intermediate states. |
2414. Length of the Longest Alphabetical Continuous Substring | Leetcode Weekly 311 | LeetCode 2414 • Bro Coders • 955 views views
Watch 9 more video solutions →Practice Length of the Longest Alphabetical Continuous Substring with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor