Medium

题目描述

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

例如，“abc” 是一个字母序连续字符串，而 “acb” 和 “za” 不是。

给你一个仅由小写字母组成的字符串 s，返回其中最长的字母序连续子字符串的长度。

示例 1：

输入：s = "abacaba"
输出：2
解释：有 4 个不同的连续子字符串："a"、"b"、"c" 和 "ab"。
"ab" 是最长的连续子字符串。

示例 2：

输入：s = "abcde"
输出：5
解释："abcde" 是最长的连续子字符串。

约束条件：

  • 1 <= s.length <= 10^5
  • s 仅由英文小写字母组成

提示：

  • 最长可能的连续子字符串是什么？
  • 最长可能的连续子字符串的大小最多为 26，所以我们可以直接暴力求解。

解题思路

解题思路

这道题要求找到最长的字母序连续子字符串，即字符按照字母表顺序连续出现的子字符串。

方法一：一次遍历（推荐）

最直接的方法是使用一次遍历，维护当前连续子字符串的长度：

  • 初始化当前长度为1（至少有一个字符）
  • 遍历字符串，如果当前字符是前一个字符的下一个字母，则当前长度+1
  • 否则重置当前长度为1，开始新的连续子字符串
  • 在过程中记录最大长度

方法二：滑动窗口

也可以使用滑动窗口的思想，扩展窗口直到不满足连续条件，然后收缩窗口重新开始。

复杂度优化

由于字母表只有26个字母，最长的连续子字符串不会超过26，这个特性可以用于一些优化场景。

时间复杂度为O(n)，空间复杂度为O(1)，是最优解法。

代码实现

class Solution {
public:
    int longestContinuousSubstring(string s) {
        int maxLen = 1;
        int currentLen = 1;
        
        for (int i = 1; i < s.length(); i++) {
            if (s[i] == s[i-1] + 1) {
                currentLen++;
                maxLen = max(maxLen, currentLen);
            } else {
                currentLen = 1;
            }
        }
        
        return maxLen;
    }
};

class Solution:
    def longestContinuousSubstring(self, s: str) -> int:
        max_len = 1
        current_len = 1
        
        for i in range(1, len(s)):
            if ord(s[i]) == ord(s[i-1]) + 1:
                current_len += 1
                max_len = max(max_len, current_len)
            else:
                current_len = 1
                
        return max_len

public class Solution {
    public int LongestContinuousSubstring(string s) {
        int maxLen = 1;
        int currentLen = 1;
        
        for (int i = 1; i < s.Length; i++) {
            if (s[i] == s[i-1] + 1) {
                currentLen++;
                maxLen = Math.Max(maxLen, currentLen);
            } else {
                currentLen = 1;
            }
        }
        
        return maxLen;
    }
}

/**
 * @param {string} s
 * @return {number}
 */
var longestContinuousSubstring = function(s) {
    let maxLength = 1;
    let currentLength = 1;
    
    for (let i = 1; i < s.length; i++) {
        if (s.charCodeAt(i) === s.charCodeAt(i - 1) + 1) {
            currentLength++;
            maxLength = Math.max(maxLength, currentLength);
        } else {
            currentLength = 1;
        }
    }
    
    return maxLength;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历整个字符串一次，n为字符串长度
空间复杂度O(1)只使用了常数级别的额外空间存储变量

相关题目