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

2024-09-19

题目:

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

  • 例如,"abc" 是一个字母序连续字符串,而 "acb""za" 不是。

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

示例 1:

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

示例 2:

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

提示:

  • 1 <= s.length <= 105
  • s 由小写英文字母组成

思路:

最终结果肯定是以原字符串中某一个字母为结尾,我们以dp[i]为以i索引字母为结尾的最长连续子字符串长度
	如果s[i] - s[i - 1] == 1, 那么可以增加 1, dp[i] = dp[i - 1] + 1
	否则 dp[i] = 1;

代码:

class Solution {
public:
    int longestContinuousSubstring(string s) {
        int n = s.size();
        int ans = 1;
        vector<int> dp(n, 1);  // dp[i]是以i索引字母为结尾的最长连续子字符串长度
        for (int i = 1; i < n; i++) {
            if (s[i] - s[i - 1] == 1) dp[i] = dp[i - 1] + 1;
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};