如何计算将给定字符串划分为内部无重复字符的最少子串个数?
核心实现思路
你现有代码的方向存在偏差:目前代码在枚举所有孤立的子串,但目标是对原字符串做连续切分,让每一块内部字符无重复,同时总切分数量最少,枚举孤立子串的逻辑无法支撑连续划分的求解。
这个问题用贪心策略就能达到最优解,不需要枚举所有可能的划分组合:
- 要让总划分数量最少,每一步只需要从当前位置出发,切出最长的、内部无重复字符的连续块就行。因为如果当前块切得比最长允许的长度更短,后续剩下的字符串更长,只会让总划分数变多,不可能比“切最长块”的方案结果更好。
具体实现步骤
- 维护一个集合,记录当前正在构建的划分块里已经出现过的字符,用来快速判断是否出现重复。
- 初始化划分计数为1(字符串非空时至少有1个块)。
- 从左到右逐位遍历字符串:
- 如果当前字符没在当前块的集合里,就把它加入集合,继续遍历。
- 如果当前字符已经在集合里,说明当前块不能再延长了,切分新块:划分计数加1,清空集合,把当前字符作为新块的第一个字符加入集合。
- 遍历完成后返回划分计数即可。
修正后的Java代码
import java.util.HashSet; import java.util.Set; class Solution { static int distinctSubString(String S) { // 边界处理:空字符串返回0 if (S == null || S.isEmpty()) { return 0; } int splitCount = 1; Set<Character> currentBlockChars = new HashSet<>(); for (char c : S.toCharArray()) { // 遇到重复字符,切分新块 if (currentBlockChars.contains(c)) { splitCount++; currentBlockChars.clear(); } currentBlockChars.add(c); } return splitCount; } // 效果验证 public static void main(String[] args) { System.out.println(distinctSubString("cycle")); // 输出2,匹配示例 System.out.println(distinctSubString("aaaa")); // 输出4,匹配示例 } }
方案有效性说明
- 时间复杂度:仅对字符串做一次遍历,为
O(n),远优于你之前枚举所有子串的O(n²)复杂度。
贪心策略的正确性可以通过反证验证:如果存在比贪心方案更少的划分,必然存在某一个块没有取到最长的合法长度,这时候可以延长该块的长度,减少后续的块数,和“更少划分”的假设矛盾,因此贪心结果是全局最优的。
内容的提问来源于stack exchange,提问作者Learner
相关产品推荐
相关产品推荐

