LeetCode 2405中等贪心/哈希
字符串的最优划分 图解题解
这道题到底在问什么
给定只含小写字母的字符串 s。把它划分成若干连续子串,要求每个子串内部字符互不相同。返回所需的最少子串数量。
- 输入
- s = "abacaba"
- 输出
- 4 （ab | ac | ab | a）
- 输入
- s = "ssssss"
- 输出
- 6 （每个 s 都得单独成段）
- 输入
- s = "abcdef"
- 输出
- 1 （整串无重复,一段即可）
最优解：一步一步想明白
- 3记住「字符不重复就并入当前段,一旦重复就切一刀、清空集合另起一段」，下面每帧都在套它。
- 4开局:还没读任何字符，当前段是空的，段数先记 1（最少也得有一段）。
- 5扫到第 0 个字符 'a'。它不在当前段字符集里，加进来仍不重复，可以并入当前段。
- 6把 'a' 放进集合（高亮行），当前段延长为 "a"。段数不变，继续往后扫。
- 7扫到第 1 个字符 'b'。它不在当前段字符集里，加进来仍不重复，可以并入当前段。
- 8把 'b' 放进集合（高亮行），当前段延长为 "ab"。段数不变，继续往后扫。
- 9扫到第 2 个字符 'a'，可它已经在当前段集合里了（高亮行）。当前段再装它就会重复，必须在这里切断。
- 10切一刀:段数加到 2，集合清空，新的一段从 'a' 重新开始（蓝色是已切走的旧段，紫框是新段）。
- 11扫到第 3 个字符 'c'。它不在当前段字符集里，加进来仍不重复，可以并入当前段。
- 12把 'c' 放进集合（高亮行），当前段延长为 "ac"。段数不变，继续往后扫。
- 13扫到第 4 个字符 'a'，可它已经在当前段集合里了（高亮行）。当前段再装它就会重复，必须在这里切断。
- 14切一刀:段数加到 3，集合清空，新的一段从 'a' 重新开始（蓝色是已切走的旧段，紫框是新段）。
- 15扫到第 5 个字符 'b'。它不在当前段字符集里，加进来仍不重复，可以并入当前段。
- 16把 'b' 放进集合（高亮行），当前段延长为 "ab"。段数不变，继续往后扫。
- 17扫到第 6 个字符 'a'，可它已经在当前段集合里了（高亮行）。当前段再装它就会重复，必须在这里切断。
- 18切一刀:段数加到 4，集合清空，新的一段从 'a' 重新开始（蓝色是已切走的旧段，紫框是新段）。
- 19扫到第 7 个字符 'c'。它不在当前段字符集里，加进来仍不重复，可以并入当前段。
- 20把 'c' 放进集合（高亮行），当前段延长为 "ac"。段数不变，继续往后扫。
- 21扫到第 8 个字符 'e'。它不在当前段字符集里，加进来仍不重复，可以并入当前段。
- 22把 'e' 放进集合（高亮行），当前段延长为 "ace"。段数不变，继续往后扫。
- 23整串扫完，一路切了 3 刀，得到 4 段：ab | ac | ab | ace，每段内部都没有重复字符。最少划分段数 = 4。
⚠️ 容易写错的地方
✗ 错：段数初始化为 0
✓ 对：初始化为 1
至少有一段;遇到一次重复才再加一段，初值 0 会比真实段数少 1
✗ 错：切断后忘记清空集合
✓ 对：切断时必须清空集合
新段是干净的，旧段用过的字符不该再约束新段，否则会多切
✗ 错：切断时只清空、忘了把当前字符放进新段
✓ 对：清空后立刻把当前字符加入
当前字符属于新段的第一个字符，漏放会导致下一次重复判断出错
完整代码（Python / C++ / Java）
Python
class Solution:
def partitionString(self, s: str) -> int:
seen = set()
ans = 1
for ch in s:
if ch in seen:
ans += 1
seen.clear()
seen.add(ch)
return ansC++
#include <string>
#include <unordered_set>
using namespace std;
class Solution {
public:
int partitionString(string s) {
unordered_set<char> seen;
int ans = 1;
for (char c : s) {
if (seen.count(c)) { ans++; seen.clear(); }
seen.insert(c);
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int partitionString(String s) {
Set<Character> seen = new HashSet<>();
int ans = 1;
for (char c : s.toCharArray()) {
if (seen.contains(c)) {
ans++;
seen.clear();
}
seen.add(c);
}
return ans;
}
}复杂度
时间
O(n)
每个字符只读一次
空间
O(1)
集合最多装 26 个小写字母
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 字符串的最优划分 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
能不能不用集合，改用别的结构？+
可以用一个长度 26 的布尔数组(或一个 26 位的位掩码)代替集合，判断「是否已见」和「清空」都是 O(1)，常数更小。本质都是维护「当前段用过哪些字母」这一信息。
这题为什么贪心一定对？+
关键是「切断只发生在被迫时」。当前段在不产生重复的前提下能延多长就延多长，没有浪费任何延长机会;若提前切断，后面只会需要同样多甚至更多的段。因此局部最优(每段最长)累加成全局最优(段数最少)。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 字符串的最优划分 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。