[LeetCode] 2405. Optimal Partition of String

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 the minimum 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 <= 105
• s consists of only English lowercase letters.

子字符串的最优划分。

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/optimal-partition-of-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路是贪心。我们用一个数组 map 记录遍历到的所有字母，变量 count 记录当前分了几段。当第二次遇到某个字母的时候，那就说明我们需要分段了。此时把 map 清空并再次记录当前遍历到的字母。注意有可能整个 input 字符串是没有重复字母的所以 count 初始化是 1。

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     public int partitionString(String s) {
 3         boolean[] map = new boolean[26];
 4         int count = 1;
 5         int i = 0;
 6         while (i < s.length()) {
 7             char c = s.charAt(i++);
 8             if (map[c - 'a'] == false) {
 9                 map[c - 'a'] = true;
10             } else {
11                 count++;
12                 Arrays.fill(map, false);
13                 map[c - 'a'] = true;
14             }
15         }
16         return count;
17     }
18 }

LeetCode 题目总结