You need to enable JavaScript to run this app. 如何计算将给定字符串划分为内部无重复字符的最少子串个数?
优惠活动
大模型
产品
解决方案
定价
更多

如何计算将给定字符串划分为内部无重复字符的最少子串个数?

核心实现思路

你现有代码的方向存在偏差:目前代码在枚举所有孤立的子串,但目标是对原字符串做连续切分,让每一块内部字符无重复,同时总切分数量最少,枚举孤立子串的逻辑无法支撑连续划分的求解。
这个问题用贪心策略就能达到最优解,不需要枚举所有可能的划分组合:

  • 要让总划分数量最少,每一步只需要从当前位置出发,切出最长的、内部无重复字符的连续块就行。因为如果当前块切得比最长允许的长度更短,后续剩下的字符串更长,只会让总划分数变多,不可能比“切最长块”的方案结果更好。

具体实现步骤

  • 维护一个集合,记录当前正在构建的划分块里已经出现过的字符,用来快速判断是否出现重复。
  • 初始化划分计数为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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.12 15:45:03