What is the optimal approach for partitioning a string into substrings with unique characters?

The optimal approach is to use a greedy strategy, where you iterate through the string and track characters using a set. When a repeat character is found, a new substring starts.

How can I improve the efficiency of my solution for partitioning strings?

By using a set to track unique characters, you can check for duplicates in constant time, ensuring the solution runs in O(n) time.

What is the time complexity of the optimal partition of string problem?

The time complexity is O(n), where n is the length of the string, as each character is processed once.

How do I handle edge cases for the optimal partition of string problem?

Edge cases include strings with all unique characters or strings with repeated characters. Handle them by properly managing the set to track unique characters in substrings.

What does 'Greedy choice plus invariant validation' mean for this problem?

It refers to making a greedy choice at each step (choosing unique characters for each substring) and validating the partition's correctness by ensuring no character repeats within a substring.

#2405

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

子字符串的最优划分

给你一个字符串 s ，请你将该字符串划分成一个或多个子字符串，并满足每个子字符串中的字符都是唯一的。也就是说，在单个子字符串中，字母的出现次数都不超过一次。满足题目要求的情况下，返回最少需要划分多少个子字符串。注意，划分后，原字符串中的每个字符都应该恰好属于一个子字符串。示例…

哈希表字符串贪心

题目描述

给你一个字符串 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⁵
s 仅由小写英文字母组成

lightbulb

解题思路

方法一：贪心

根据题意，每个子字符串应该尽可能长，且包含的字符唯一，因此，我们只需要贪心地进行划分即可。

我们定义一个二进制整数 $\textit{mask}$ 来记录当前子字符串中出现的字符，其中 $\textit{mask}$ 的第 $i$ 位为 $1$ 表示第 $i$ 个字母已经出现过，为 $0$ 表示未出现过。另外，我们还需要一个变量 $\textit{ans}$ 来记录划分的子字符串个数，初始时 $\textit{ans} = 1$ 。

遍历字符串 $s$ 中的每个字符，对于每个字符 $c$ ，我们将其转换为 $0$ 到 $25$ 之间的整数 $x$ ，然后判断 $\textit{mask}$ 的第 $x$ 位是否为 $1$ ，如果为 $1$ ，说明当前字符 $c$ 与当前子字符串中的字符有重复，此时 $\textit{ans}$ 需要加 $1$ ，并将 $\textit{mask}$ 置为 $0$ ；否则，将 $\textit{mask}$ 的第 $x$ 位置为 $1$ 。然后，我们将 $\textit{mask}$ 更新为 $\textit{mask}$ 与 $2^x$ 的按位或结果。

最后，返回 $\textit{ans}$ 即可。

时间复杂度 $O(n)$ ，其中 $n$ 为字符串 $s$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def partitionString(self, s: str) -> int:
        ans, mask = 1, 0
        for x in map(lambda c: ord(c) - ord("a"), s):
            if mask >> x & 1:
                ans += 1
                mask = 0
            mask |= 1 << x
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate identify and implement a greedy solution to handle substrings with unique characters?
question_mark
Does the candidate consider edge cases in the problem, such as all characters being the same or all characters being unique?
question_mark
Is the candidate able to explain how set operations play a role in partitioning the string?

warning

常见陷阱

外企场景

error
Failing to handle strings with all unique or all same characters properly.
error
Misunderstanding the need to track only unique characters within each substring.
error
Not using an efficient data structure like a set to track characters within the substring.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the string contains digits instead of lowercase letters?
arrow_right_alt
Can the algorithm handle uppercase letters or a mixture of uppercase and lowercase?
arrow_right_alt
How would you adapt this solution for strings with a larger character set, like Unicode characters?

help

常见问题

外企场景

继续练习

#2384 最大回文数字 #2434 使用机器人打印字典序最小的字符串 #2182 构造限制重复的字符串