Medium

题目描述

给你一个字符串 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. 维护一个集合来记录当前子字符串中已出现的字符
  2. 从左到右遍历字符串，对于每个字符：
    • 如果该字符已在当前子字符串中出现过，说明需要开始新的子字符串
    • 否则，将该字符加入当前子字符串

算法步骤：

  1. 初始化一个哈希集合用于记录当前子字符串的字符
  2. 初始化分割数量为1（至少需要一个子字符串）
  3. 遍历字符串：
    • 如果当前字符已存在于集合中，增加分割数量，清空集合
    • 将当前字符添加到集合中
  4. 返回分割数量

为什么贪心策略是正确的？ 因为我们总是尽可能延长每个子字符串，这样能保证使用最少的分割次数。如果提前分割，只会增加不必要的分割数量。

时间复杂度： O(n)，其中n是字符串长度 空间复杂度： O(1)，因为最多只有26个小写字母

代码实现

class Solution {
public:
    int partitionString(string s) {
        unordered_set<char> seen;
        int partitions = 1;
        
        for (char c : s) {
            if (seen.count(c)) {
                partitions++;
                seen.clear();
            }
            seen.insert(c);
        }
        
        return partitions;
    }
};

class Solution:
    def partitionString(self, s: str) -> int:
        seen = set()
        partitions = 1
        
        for c in s:
            if c in seen:
                partitions += 1
                seen.clear()
            seen.add(c)
        
        return partitions

public class Solution {
    public int PartitionString(string s) {
        HashSet<char> seen = new HashSet<char>();
        int partitions = 1;
        
        foreach (char c in s) {
            if (seen.Contains(c)) {
                partitions++;
                seen.Clear();
            }
            seen.Add(c);
        }
        
        return partitions;
    }
}

/**
 * @param {string} s
 * @return {number}
 */
var partitionString = function(s) {
    const seen = new Set();
    let partitions = 1;
    
    for (const c of s) {
        if (seen.has(c)) {
            partitions++;
            seen.clear();
        }
        seen.add(c);
    }
    
    return partitions;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历字符串一次，每次操作都是O(1)
空间复杂度O(1)哈希集合最多存储26个小写字母，为常数空间

相关题目