Watch 10 video solutions for Length of the Longest Alphabetical Continuous Substring, a medium level problem involving String. This walkthrough by Bro Coders has 955 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |