[LeetCode] 2414. Length of the Longest Alphabetical Continuous Substring

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 <= 105
s consists of only English lowercase letters.

最长的字母序连续子字符串的长度。

字母序连续字符串 是由字母表中连续字母组成的字符串。换句话说，字符串 "abcdefghijklmnopqrstuvwxyz" 的任意子字符串都是 字母序连续字符串 。

例如，”abc” 是一个字母序连续字符串，而 “acb” 和 “za” 不是。
给你一个仅由小写英文字母组成的字符串 s ，返回其 最长 的 字母序连续子字符串 的长度。

思路

判断两个字母是否是字母表中连续的字母，就是去判断他们 ASCII 码的差值是否为 1。而且这道题降低了难度，”za” 这样的字母序是不算作连续的字符串的。

思路是双指针，我们需要两个指针，左指针指向当前字母，右指针从下一个字母开始一直往右走，判断两个指针指向的字母的 ASCII 码的差值是否等于两个指针下标的差。如果是，则说明这两个字母是连续的，我们需要更新最长的字母序连续子字符串的长度。

复杂度

时间O(n)，n 是字符串 s 的长度。
空间O(1)，只需要常数的空间。

代码

Java实现

class Solution {
    public int longestContinuousSubstring(String s) {
        // corner case
        if (s == null || s.length() == 0) {
            return 0;
        }

        // normal case
        int res = 0;
        int i = 0;
        while (i < s.length()) {
            int start = i;
            while (i < s.length() && i - start == s.charAt(i) - s.charAt(start)) {
                i++;
            }
            res = Math.max(res, i - start);
        }
        return res;
    }
}

还有一种更简便的做法是用 for 循环，判断当前字母的 ASCII 码是否比上一个字母的 ASCII 码大 1，如果是，则说明这两个字母是连续的，我们需要更新最长的字母序连续子字符串的长度；如果不是则说明这两个字母不是连续的，我们需要重新开始。

Java实现

class Solution {
    public int longestContinuousSubstring(String s) {
        int res = 1;
		int count = 1;
		for (int i = 1; i < s.length(); i++) {
			if (s.charAt(i) - s.charAt(i - 1) == 1) {
				count++;
				res = Math.max(res, count);
			} else {
				count = 1;
			}
		}
		return res;
    }
}