1446. 连续字符#

题目描述#

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

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

示例 1：

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

示例 2：

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

提示：

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

解题思路#

核心思想#

用分组循环把字符串划分成若干「连续相同字符」的段，取最长的段长度。灵茶山艾府题单里”分组循环”的经典骨架是「外层遍历段起点，内层扩展段终点」。

对每个段起点 i，用 j 向前扩展，直到 s[j+1] 与 s[i] 不同，此时 [i, j] 就是一个最长连续相同字符段，长度为 j - i + 1，用它更新答案，然后 i 跳到 j+1 开始下一段。

分组示意（s = “abbccc”）：

1
a | b b | c c c
2
段长 1   2   3   → 答案 3

算法步骤#

初始化 ans = 1（至少有一个字符），i = 0。
当 i < n 时：
- j = i，内层 while j+1 < n and s[j+1] == s[i] 时 j++；
- ans = max(ans, j - i + 1)；
- i = j + 1。
返回 ans。

逐步举例#

以 s = "abbcccddddeeeeedcba" 为例，最长为最后的 e 段：

段	区间	长度
a	[0,0]	1
bb	[1,2]	2
ccc	[3,5]	3
dddd	[6,9]	4
eeeeee	[10,15]	5
d	[16,16]	1
c	[17,17]	1
b	[18,18]	1
a	[19,19]	1

答案为 5。

复杂度分析#

时间复杂度：O(N)，每个下标只被访问常数次。
空间复杂度：O(1)。

代码实现#

1
class Solution:
2
    def maxPower(self, s: str) -> int:
3
        n = len(s)
4
        ans = 1
5
        i = 0
6
        while i < n:
7
            j = i
8
            while j + 1 < n and s[j + 1] == s[i]:
9
                j += 1
10
            ans = max(ans, j - i + 1)
11
            i = j + 1
12
        return ans

1
import sys
2
from pathlib import Path
3

4
sys.path.insert(0, str(Path(__file__).parent))
5
import unittest
6

7
from solution import Solution
8

9

10
class TestSolution(unittest.TestCase):
11
    def test_example1(self):
12
        self.assertEqual(Solution().maxPower("leetcode"), 2)
13

14
    def test_example2(self):
15
        self.assertEqual(Solution().maxPower("abbcccddddeeeeedcba"), 5)
16

17

18
if __name__ == '__main__':
19
    unittest.main()