题目:
字母序连续字符串 是由字母表中连续字母组成的字符串。换句话说,字符串 "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;
}
};