1446-连续字符

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:25 2023-09-13 16:06:25 Updated    

给你一个字符串 s ，字符串的 「能量」 定义为：只包含一种字符的最长非空子字符串的长度。

请你返回字符串 s 的 能量 。

示例 1：

**输入：** s = "leetcode"
**输出：** 2
**解释：** 子字符串 "ee" 长度为 2 ，只包含字符 'e' 。

示例 2：

**输入：** s = "abbcccddddeeeeedcba"
**输出：** 5
**解释：** 子字符串 "eeeee" 长度为 5 ，只包含字符 'e' 。

提示：

  • 1 <= s.length <= 500
  • s 只包含小写英文字母。

方法一：一次遍历

题目中的「只包含一种字符的最长非空子字符串的长度」，即为某个字符连续出现次数的最大值。据此可以设计如下算法来求解：

初始化当前字符连续出现次数 cnt 为 1。

从 s[1] 开始，向后遍历字符串，如果 s[i]=s[i-1]，则将 cnt 加一，否则将 cnt 重置为 1。

维护上述过程中 cnt 的最大值，即为答案。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
class Solution:
    def maxPower(self, s: str) -> int:
        ans, cnt = 1, 1
        for i in range(1, len(s)):
            if s[i] == s[i - 1]:
                cnt += 1
                ans = max(ans, cnt)
            else:
                cnt = 1
        return ans
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxPower(string s) {
        int ans = 1, cnt = 1;
        for (int i = 1; i < s.length(); ++i) {
            if (s[i] == s[i - 1]) {
                ++cnt;
                ans = max(ans, cnt);
            } else {
                cnt = 1;
            }
        }
        return ans;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maxPower(String s) {
        int ans = 1, cnt = 1;
        for (int i = 1; i < s.length(); ++i) {
            if (s.charAt(i) == s.charAt(i - 1)) {
                ++cnt;
                ans = Math.max(ans, cnt);
            } else {
                cnt = 1;
            }
        }
        return ans;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public int MaxPower(string s) {
        int ans = 1, cnt = 1;
        for (int i = 1; i < s.Length; ++i) {
            if (s[i] == s[i - 1]) {
                ++cnt;
                ans = Math.Max(ans, cnt);
            } else {
                cnt = 1;
            }
        }
        return ans;
    }
}
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func maxPower(s string) int {
    ans, cnt := 1, 1
    for i := 1; i < len(s); i++ {
        if s[i] == s[i-1] {
            cnt++
            if cnt > ans {
                ans = cnt
            }
        } else {
            cnt = 1
        }
    }
    return ans
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
var maxPower = function(s) {
    let ans = 1, cnt = 1;
    for (let i = 1; i < s.length; ++i) {
        if (s[i] == s[i - 1]) {
            ++cnt;
            ans = Math.max(ans, cnt);
        } else {
            cnt = 1;
        }
    }
    return ans;
};

复杂度分析

  • 时间复杂度：O(n)，其中 n 是字符串 s 的长度。遍历一次 s 的时间复杂度为 O(n)。

  • 空间复杂度：O(1)。我们只需要常数的空间保存若干变量。

 Comments
On this page
1446-连续字符