Description
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 <= 105sconsists of only English lowercase letters.
Solutions
Solution 1: Single Pass
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).
class Solution: def longestContinuousSubstring(self, s: str) -> int: ans = cnt = 1 for x, y in pairwise(map(ord, s)): if y - x == 1: cnt += 1 ans = max(ans, cnt) else: cnt = 1 return ans(code-box)
