LeetCode 1446. 连续字符

2021-06-22 HGNULB 约 8 分钟

文章信息 6 个分类 1 个标签

分类

LeetCode CodeTop 简单未解决 1-2 快手

题目描述

✅ 1446. 连续字符

题意分析

给一个字符串 s，找出「只由同一个字符构成的连续子串」中最长的那一段，返回它的长度。题目管这个值叫「能量」。要的是长度，不是那个字符本身，也不是子串。

「连续」两个字必须抠死：aabaa 的答案是 2 而不是 4——两段 aa 中间被 b 隔开，不能合并计数。这道题问的是极长同字符段（run），不是某个字符在全串中的出现次数。

约束里的信号：s 长度到 500，全是小写字母，且保证非空。非空这一点很重要，它让「答案至少是 1」成为可以直接用的初值；如果题目允许空串，返回值就得单独讨论。字符集是小写字母意味着不需要额外的字符归一化处理。

边界有三类：整串只有一个字符（答案 1）；整串全是同一个字符（答案就是串长）；相邻字符两两都不同，例如 abcde（答案 1，每段长度都是 1）。最容易被忽略的边界是「最长段恰好落在字符串末尾」，比如 abbb——如果只在段结束时才结算答案，末尾这段没有「下一个不同字符」来触发结算，就会被漏掉。

解法：模拟流程

核心思路

暴力写法是枚举所有子串再逐个检查是否同字符，$O(n^3)$；稍作优化，枚举左端点后向右扩展到第一个不同的字符，$O(n^2)$。但只要观察一下这个 $O(n^2)$ 的过程就会发现大量重复：从 aaaa 的下标 0 出发扩展了 4 步，从下标 1 出发又扩展 3 步，同一段被反复走了很多遍。

真正的观察是：极长同字符段之间互不重叠，整个字符串被这些段完整地切分。因此不需要「枚举起点再扩展」，只要沿着字符串走一遍，在每个位置判断「我和前一个字符相同吗」，就能知道当前段是延续还是重新开始。每个位置只被访问一次。

于是维护两个变量，并写死它们的含义：cur 表示以当前下标 i 结尾的同字符连续段的长度，maxLen 表示已扫描过的所有位置中 cur 的最大值。

循环不变量是：每轮循环结束时，cur 恰好等于以 i 结尾的极长同字符段长度，且 maxLen 等于下标 0..i 范围内所有 cur 的最大值。维持它只需要一条转移规则——s[i] == s[i-1] 时 cur 加 1，否则 cur 重置为 1（新段从 i 自己开始，长度是 1 而不是 0）——外加每轮都用 cur 更新一次 maxLen。

因为不变量要求 maxLen 在每个位置都被更新，而不是只在段结束时更新，末尾那段自然被覆盖，不需要循环后补一次结算。这正是「以 i 结尾」这种状态定义相对于「段的起止区间」定义的优势。

正确性可直接由归纳得到：下标 0 的段长为 1；到达 i 时，若相邻字符相同，当前段只能由 i-1 的段延长一位，否则任何同字符段都不能跨过边界，只能从 i 重新取长度 1。于是 cur 始终精确，逐位置取最大后的 maxLen 也必然覆盖全局最长段。

解题步骤

初始化：maxLen = 1、cur = 1。两个初值都取 1，含义是「下标 0 自己构成一个长度为 1 的段」。题目保证 s 非空，所以下标 0 一定存在，取 1 是安全的；如果初始化成 0，s = "a" 这种输入会直接返回 0。

从下标 1 开始遍历：下标 0 没有前驱，无法参与「与前一个字符比较」的判断，它的结果已经被初始化吸收掉了。从 0 开始遍历会在 i - 1 = -1 处越界。

延续或重启：s[i] == s[i-1] 时 cur++，表示当前段又长了一位；否则 cur = 1，表示前一段在 i - 1 处终结，新段从 i 开始。重置成 1 而不是 0，是因为 s[i] 自己已经构成了一个长度 1 的段。

每轮都更新答案：maxLen = max(maxLen, cur)。这一行必须放在 if/else 之外、循环体的末尾，保证每个下标的 cur 都被考察过。放进 else 分支里（只在段切换时结算）就会漏掉以末位结尾的段。

返回 maxLen，不是 cur（cur 只是最后一段的长度），也不是段的起止下标。

以 s = "abbcccddddb" 走一遍，逐位记录 (字符, cur, maxLen)。

初始：cur = 1、maxLen = 1，对应下标 0 的 a。

i = 1 的 b：与前一个 a 不同，cur 重置为 1，maxLen 仍是 1。
i = 2 的 b：与前一个 b 相同，cur = 2，maxLen = 2。
i = 3 的 c：不同，cur = 1，maxLen = 2。
i = 4 的 c：相同，cur = 2，maxLen = 2。
i = 5 的 c：相同，cur = 3，maxLen = 3。
i = 6 的 d：不同，cur = 1，maxLen = 3。
i = 7 的 d：相同，cur = 2，maxLen = 3。
i = 8 的 d：相同，cur = 3，maxLen = 3。
i = 9 的 d：相同，cur = 4，maxLen = 4。
i = 10 的 b：不同，cur = 1，maxLen = 4。

返回 4，对应 dddd。注意最后一个 b 与开头的 b、中间的 bb 都不相邻，各自独立成段，验证了「连续」的语义。若把用例换成 "abbccc"，最长段 ccc 正好在末尾，因为每轮都更新 maxLen，i = 5 时 maxLen 就已经变成 3，不需要循环后再补一次。

代码实现

class Solution {
    public int maxPower(String s) {
        // cur：以当前下标结尾的同字符连续段长度；题目保证 s 非空，故初值取 1。
        int maxLen = 1;
        int cur = 1;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == s.charAt(i - 1)) {
                cur++;
            } else {
                // 新段从 i 自己开始，长度是 1 而不是 0。
                cur = 1;
            }
            // 每个位置都结算一次，末尾那段无需循环外补算。
            maxLen = Math.max(maxLen, cur);
        }
        return maxLen;
    }
}

func maxPower(s string) int {
	// cur：以当前下标结尾的同字符连续段长度；题目保证 s 非空，故初值取 1。
	maxLen := 1
	cur := 1
	for i := 1; i < len(s); i++ {
		if s[i] == s[i-1] {
			cur++
		} else {
			// 新段从 i 自己开始，长度是 1 而不是 0。
			cur = 1
		}
		// 每个位置都结算一次，末尾那段无需循环外补算。
		if cur > maxLen {
			maxLen = cur
		}
	}
	return maxLen
}

复杂度分析

时间复杂度：$O(n)$。单趟遍历，每个下标只做一次字符比较、一次加法或赋值、一次取最大，全是常数操作，没有回退也没有嵌套。

空间复杂度：$O(1)$。只用了 cur 和 maxLen 两个整数，与串长无关，也不创建任何子串。

关键点总结

状态定义成「以 i 结尾的段长」而不是「段的起止区间」，是本题最值得迁移的一点。前者让答案在每个位置都能结算，天然覆盖末尾段，省掉循环后的补算逻辑；后者则必须处理「最后一段没有终止信号」的特例。

重置写 cur = 1 而非 cur = 0：新段的第一个元素就是当前字符本身。这个 off-by-one 在所有「分段计数」题里都一样。

遍历从下标 1 开始，下标 0 的贡献由初始值承担。这样比在循环里写 i == 0 特判更干净。

更新答案的语句放在分支之外。面试时被问「为什么不放进 else 里更省」，要能立刻答出「末尾段没有下一次切换来触发结算」。

题目保证非空才敢把初值设为 1。如果面试官把条件放宽到允许空串，要主动提出返回 0 的特判——这类「初值合法性依赖题目约束」的讨论是加分项。

易错点总结

maxLen 和 cur 初始化为 0：s = "a" 时循环一次都不进，直接返回 0，正确答案是 1。

把更新答案的语句写进 else 分支：s = "ccc" 全程不会触发 else，答案停在初值 1，而正确答案是 3。末尾段会被系统性漏掉。

重置时写 cur = 0：s = "ab" 时 i = 1 处 cur 变成 0，maxLen 仍是 1，看似侥幸正确；但 s = "aab" 会让末位 b 的段长记成 0，若再遇到 s = "abb"，i = 1 重置为 0、i = 2 加到 1，返回 1 而正确答案是 2。

从下标 0 开始遍历：i = 0 时访问 s[-1]，Java 抛 StringIndexOutOfBoundsException，Go 直接 panic。

返回 cur 而不是 maxLen：s = "aaab" 的 cur 在结束时是 1（最后一段 b），返回 1，正确答案是 3。

误解「连续」为「出现次数」：s = "aabaa" 若统计字符总频次会返回 4，正确答案是 2，两段 aa 被 b 隔断不能合并。

在循环里用 s.substring(...) 或字符串拼接来记录当前段：s 长度 500 时会产生大量临时字符串，时间退化到 $O(n^2)$、空间同样退化，而且完全没有必要——只需要长度不需要内容。

用哈希表统计每个字符的最大段长再取最大：多余的 $O(26)$ 空间不算错，但常见的写法是「进入新段时才写表」，s = "aab" 的末段若忘记在循环后落表就会丢失，白白增加出错面。

Go 里对含多字节字符的串按 range 遍历取 rune 却仍用 s[i-1] 取字节：本题限定小写字母不会触发，但把同样代码套到含中文的变体上，字节索引和 rune 索引会错位，比较结果全乱。

相似题目

题目	难度	考察点
485. 最大连续 1 的个数	简单	同一骨架但只关心值为 1 的段，遇到 0 直接清零，判断条件更简单
674. 最长连续递增序列	简单	延续条件从「与前一个相等」换成「严格大于前一个」，重置逻辑一致
1004. 最大连续1的个数 III	中等	允许翻转 k 个 0，段不再是纯粹的同值段，必须升级成可伸缩窗口
424. 替换后的最长重复字符	中等	允许替换 k 个字符，需要窗口内的最高频字符计数来判断合法性
3. 无重复字符的最长子串	中等	约束反过来是「段内字符互不相同」，重置变成按上次出现位置跳跃
1047. 删除字符串中的所有相邻重复项	简单	同样围绕相邻相同字符，但要真的消除它们并处理消除后新产生的相邻对