2405.md

title	description	keywords
2405. 子字符串的最优划分	LeetCode 2405. 子字符串的最优划分题解，Optimal Partition of String，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 2405. 子字符串的最优划分 子字符串的最优划分 Optimal Partition of String 解题思路 贪心 哈希表 字符串

2405. 子字符串的最优划分

🟠 Medium  🔖  贪心 哈希表 字符串  🔗 力扣 LeetCode

题目

Given a string s, partition the string into one or more substrings such that the characters in each substring are unique. That is, no letter appears in a single substring more than once.

Return theminimum number of substrings in such a partition.

Note that each character should belong to exactly one substring in a partition.

Example 1:

Input: s = "abacaba"

Output: 4

Explanation:

Two possible partitions are ("a","ba","cab","a") and ("ab","a","ca","ba").

It can be shown that 4 is the minimum number of substrings needed.

Example 2:

Input: s = "ssssss"

Output: 6

Explanation: The only valid partition is ("s","s","s","s","s","s").

Constraints:

• 1 <= s.length <= 10^5
• s consists of only English lowercase letters.

题目大意

给你一个字符串 s ，请你将该字符串划分成一个或多个 子字符串 ，并满足每个子字符串中的字符都是 唯一 的。也就是说，在单个子字符串中，字母的出现次数都不超过 一次 。

满足题目要求的情况下，返回 最少 需要划分多少个子字符串。

注意，划分后，原字符串中的每个字符都应该恰好属于一个子字符串。

示例 1：

输入： s = "abacaba"

输出： 4

解释：

两种可行的划分方法分别是 ("a","ba","cab","a") 和 ("ab","a","ca","ba") 。

可以证明最少需要划分 4 个子字符串。

示例 2：

输入： s = "ssssss"

输出： 6

解释： 只存在一种可行的划分方法 ("s","s","s","s","s","s") 。

提示：

• 1 <= s.length <= 10^5
• s 仅由小写英文字母组成

解题思路

1. 使用集合 charSet 来存储当前子串中的字符。集合的查找时间复杂度为 O(1)，可以高效判断字符是否已存在。
2. 遍历字符串中的每个字符 char：
   • 如果 char 不在集合中，将字符 char 添加到集合中。
   • 如果 char 在集合中已经存在（即重复），则意味着当前子串无法继续扩展，增加子串计数 count，并重置集合，开始新的子串。
3. 遍历完成后，返回 count，即划分后的子串数量。

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串 s 的长度。遍历字符串一次，每次查找字符是否在集合中的操作为常数时间 O(1)，整体时间复杂度为 O(n)。
• 空间复杂度：O(k)，其中 k 是当前子串的最大字符数。在最坏情况下，k 的大小可能为字符串 s 的长度，空间复杂度为 O(n)。

代码

/**
 * @param {string} s
 * @return {number}
 */
var partitionString = function (s) {
	let charSet = new Set(); // 用集合存储当前子串的字符
	let count = 1; // 初始子串数为1
	for (let char of s) {
		if (charSet.has(char)) {
			count++; // 当前子串结束，增加子串计数
			charSet.clear(); // 重置集合
		}
		charSet.add(char); // 将字符添加到当前子串集合
	}
	return count;
};

相关题目

题号	标题	题解	标签	难度	力扣
3	无重复字符的最长子串	[✓]	哈希表 字符串 滑动窗口	🟠	🀄️ 🔗
395	至少有 K 个重复字符的最长子串		哈希表 字符串 分治 1+	🟠	🀄️ 🔗
763	划分字母区间	[✓]	贪心 哈希表 双指针 1+	🟠	🀄️ 🔗
915	分割数组		数组	🟠	🀄️ 🔗
2461	长度为 K 子数组中的最大和	[✓]	数组 哈希表 滑动窗口	🟠	🀄️ 🔗