Welcome to Subscribe On Youtube
2414. Length of the Longest Alphabetical Continuous Substring
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: Two Pointers
We use two pointers $i$ and $j$ to point to the start and end of the current consecutive substring respectively. Traverse the string $s$, if the current character $s[j]$ is greater than $s[j-1]$, then move $j$ one step to the right, otherwise update $i$ to $j$, and update the length of the longest consecutive substring.
The time complexity is $O(n)$, where $n$ is the length of the string $s$. The space complexity is $O(1)$.
-
class 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; } } -
class 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; } }; -
class 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 -
func longestContinuousSubstring(s string) int { ans := 0 i, j := 0, 1 for ; j < len(s); j++ { ans = max(ans, j-i) if s[j]-s[j-1] != 1 { i = j } } ans = max(ans, j-i) return ans } -
function longestContinuousSubstring(s: string): number { const n = s.length; let res = 1; let i = 0; for (let j = 1; j < n; j++) { if (s[j].charCodeAt(0) - s[j - 1].charCodeAt(0) !== 1) { res = Math.max(res, j - i); i = j; } } return Math.max(res, n - i); } -
impl Solution { pub fn longest_continuous_substring(s: String) -> i32 { let s = s.as_bytes(); let n = s.len(); let mut res = 1; let mut i = 0; for j in 1..n { if s[j] - s[j - 1] != 1 { res = res.max(j - i); i = j; } } res.max(n - i) as i32 } }