2026-04-13：不同首字母的子字符串数目。用go语言，给定一个只包含小写字母的字符串 s。 你需要把它切分成若干个连续、非空的子串（覆盖整个字符串，且不重叠）。 目标是：让子串的数量尽可能多，并

2026-04-13不同首字母的子字符串数目。用go语言给定一个只包含小写字母的字符串 s。你需要把它切分成若干个连续、非空的子串覆盖整个字符串且不重叠。目标是让子串的数量尽可能多并满足限制——每个子串的起始字符都必须各不相同也就是说任意两个子串的第一个字母不能相同。请输出满足上述条件时子串的最大数量。1 s.length 100000。s 仅由小写英文字母组成。输入 s “abcd”。输出 4。解释可以将 “abcd” 划分为 “a”、“b”、“c” 和 “d”。每个子字符串都以不同的字符开头。因此答案是 4。题目来自力扣3760。解题过程分步详细描述一、理解题目核心要求我们需要把给定的纯小写字母字符串分割成连续、不重叠、非空的子串满足两个关键条件所有子串的起始字符必须完全不同不能有两个子串以同一个字母开头在满足第一个条件的前提下分割出的子串数量要尽可能多。最终输出这个最大的子串数量。补充小写字母一共只有26个a-z因此最大可能的子串数量永远不会超过26这是核心限制。二、解题核心思路要让子串数量最多最优策略是尽可能把每个字符单独切分为一个子串只要这个字符还没有被用作过子串的起始字符。因为一旦某个字母作为子串开头使用过一次后续就不能再用了所以我们需要记录已经使用过的起始字母遍历字符串时逐个判断。三、分步骤执行过程以示例 s“abcd” 为例步骤1初始化记录工具创建一个标记集合/标记位专门用来记录已经被用作子串起始的字母初始状态为空没有任何字母被使用。同时初始化一个计数器用来统计最终的子串数量初始值为0。步骤2从头开始遍历字符串的每一个字符我们按顺序处理字符串中的每一个字符判断当前字符是否能作为新子串的起始字符处理第一个字符a检查a是否在已使用的起始字母集合中 → 未使用可以将a单独切分为一个子串把a加入已使用集合子串计数器 1当前计数1。处理第二个字符b检查b是否在已使用的起始字母集合中 → 未使用可以将b单独切分为一个子串把b加入已使用集合子串计数器 1当前计数2。处理第三个字符c检查c是否在已使用的起始字母集合中 → 未使用可以将c单独切分为一个子串把c加入已使用集合子串计数器 1当前计数3。处理第四个字符d检查d是否在已使用的起始字母集合中 → 未使用可以将d单独切分为一个子串把d加入已使用集合子串计数器 1当前计数4。步骤3遍历结束输出结果整个字符串遍历完成计数器的值就是最大子串数量最终结果为4。四、通用场景补充说明非示例帮助理解如果字符串出现重复字母例如sabac第一个字符a未使用切分计数1标记a第二个字符b未使用切分计数2标记b第三个字符a已标记使用过不能作为新子串开头必须和前一个子串合并即ba合并为一个子串第四个字符c未使用切分计数3标记c最终结果为3。复杂度分析1. 时间复杂度我们只需要从头到尾遍历一次字符串每个字符仅处理一次所有判断、标记操作都是常数时间 O(1)因为字母只有26个操作无额外循环总时间复杂度O(n)n 为字符串的长度。2. 额外空间复杂度我们仅使用了固定大小的空间一个整数位标记/26个布尔值标记来记录已使用的字母空间大小不随字符串长度 n 变化属于常数级空间总额外空间复杂度O(1)。总结解题核心遍历字符串标记已使用的起始字母尽可能切分单个字符为子串时间复杂度O(n)线性遍历高效适配10万长度的字符串额外空间复杂度O(1)常数空间无额外内存消耗。Go完整代码如下packagemainimport(fmtmath/bits)funcmaxDistinct(sstring)int{set:0for_,c:ranges{set|1(c-a)}returnbits.OnesCount(uint(set))}funcmain(){s:abcdresult:maxDistinct(s)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-defmax_distinct(s:str)-int:bitmask0forcins:bitmask|1(ord(c)-ord(a))returnbin(bitmask).count(1)if__name____main__:sabcdresultmax_distinct(s)print(result)C完整代码如下#includeiostream#includestring#includebitintmaxDistinct(conststd::strings){intset0;for(charc:s){set|1(c-a);}returnstd::popcount(static_castunsignedint(set));}intmain(){std::string sabcd;intresultmaxDistinct(s);std::coutresultstd::endl;return0;}