方法一:贪心

转载自灵神题解

class Solution:
    def longestContinuousSubstring(self, s: str) -> int:
        ans = start = 0
        for i in range(1, len(s)):
            if ord(s[i]) != ord(s[i - 1]) + 1:
                ans = max(ans, i - start)
                start = i  # 新起点
        return max(ans, len(s) - start)

复杂度分析

• 时间复杂度：O(n)，其中 n为 s的长度。
• 空间复杂度：O(1)，仅用到若干变量。

方法二:动态规划

本题也可以看作求字符串 "abcdefghijklmnopqrstuvwxyz"和字符串s的最长公共子序列，动态规划并不是本题的最优解，但是是通用解。

class Solution:
    def longestContinuousSubstring(self, s: str) -> int:
        target = "abcdefghijklmnopqrstuvwxyz"
        ans = 0
        n = len(s)
        f = [0]*(n)
        for i in range(n):
            for j in range(26):
                if s[i] == target[j]:
                    if j>0 and i>0:
                        f[i] = f[i-1]+1 if s[i-1]== target[j-1] else 1
                    else:
                        f[i] = 1
        return max(f)

复杂度分析

• 时间复杂度：O(mn)，其中m为字符串 "abcdefghijklmnopqrstuvwxyz"的长度， n为 s 的长度。
• 空间复杂度：O(n)。

扩展

如果本题改写成求字符串s的最长递增子序列，只要稍微更改一下灵神题解即可。

class Solution:
    def longestContinuousSubstring(self, s: str) -> int:
        ans = start = 0
        for i in range(1, len(s)):
            if ord(s[i]) < ord(s[i - 1]):
                ans = max(ans, i - start)
                start = i  # 新起点
        return max(ans, len(s) - start)

参考资料

2414. 最长的字母序连续子字符串的长度
灵神题解