763. 划分字母区间

🟠   🔖  贪心 哈希表 双指针 字符串  🔗 力扣 LeetCode

题目

You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.

Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.

Return a list of integers representing the size of these parts.

Example 1:

Input: s = "ababcbacadefegdehijhklij"

Output: [9,7,8]

Explanation:

The partition is "ababcbaca", "defegde", "hijhklij".

This is a partition so that each letter appears in at most one part.

A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits s into less parts.

Example 2:

Input: s = "eccbbbbdec"

Output: [10]

Constraints:

• 1 <= s.length <= 500
• s consists of lowercase English letters.

题目大意

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1：

输入： s = "ababcbacadefegdehijhklij"

输出：[9,7,8]

解释：

划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。

每个字母最多出现在一个片段中。

像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。

示例 2：

输入： s = "eccbbbbdec"

输出：[10]

提示：

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

解题思路

这道题的关键在于确保每个字母只出现在一个分区中。为了达到这一点，需要确定每个字母的最远出现位置，并根据这个信息进行分割。

1. 记录每个字母的最远出现位置：

   • 首先遍历字符串 s，记录每个字符在字符串中的最后一次出现的索引。这样在进行分区时，知道每个字母应该在多远的地方结束。

2. 遍历字符串并进行分区：

   • 使用两个指针 start 和 end 来定义当前分区的起始位置和结束位置。
   • 对每个字符，更新 end 为该字符的最远出现位置。继续遍历直到当前索引等于 end，此时说明当前分区完成。
   • 记录分区的长度，并将 start 更新为下一个分区的开始位置。

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串 s 的长度。需要遍历字符串两次，分别记录字符的最远出现位置和确定分区。
• 空间复杂度：O(1)，虽然使用了一个对象来存储每个字母的最后出现位置，但其大小是常数级的（最多 26 个字母），所以空间复杂度为 O(1)。

代码

/**
 * @param {string} s
 * @return {number[]}
 */
var partitionLabels = function (s) {
	let map = {},
		res = [];
	// 遍历字符串，记录每个字符的最后出现位置
	for (let i = 0; i < s.length; i++) {
		map[s[i]] = i;
	}
	let start = 0,
		end = 0;
	// 遍历字符串，根据最远的出现位置来分割
	for (let i = 0; i < s.length; i++) {
		end = Math.max(end, map[s[i]]);
		if (end == i) {
			// 记录分区长度
			res.push(end - start + 1);
			// 更新下一个分区的起始位置
			start = end + 1;
		}
	}
	return res;
};

相关题目

题号	标题	题解	标签	难度
56	合并区间	[✓]	数组 排序
2405	子字符串的最优划分		贪心 哈希表 字符串