贪心题目：划分字母区间

题目

标题和出处

标题：划分字母区间

出处：763. 划分字母区间

难度

4 级

题目描述

要求

给定字符串s \texttt{s}s。需要将这个字符串划分为尽可能多的片段，满足同一字母最多出现在一个片段中。

注意在将字符串划分成片段之后，所有片段拼接之后的结果应该是s \texttt{s}s。

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

示例

示例 1：

输入：s = "ababcbacadefegdehijhklij" \texttt{s = "ababcbacadefegdehijhklij"}s = "ababcbacadefegdehijhklij"
输出：[9,7,8] \texttt{[9,7,8]}[9,7,8]
解释：
划分结果为["ababcbaca", "defegde", "hijhklij"] \texttt{["ababcbaca", "defegde", "hijhklij"]}["ababcbaca", "defegde", "hijhklij"]。
每个字母最多出现在一个片段中。
像["ababcbacadefegde", "hijhklij"] \texttt{["ababcbacadefegde", "hijhklij"]}["ababcbacadefegde", "hijhklij"]的划分是错误的，因为划分的片段数较少。

示例 2：

输入：s = "eccbbbbdec" \texttt{s = "eccbbbbdec"}s = "eccbbbbdec"
输出：[10] \texttt{[10]}[10]

数据范围

• 1 ≤ s.length ≤ 500 \texttt{1} \le \texttt{s.length} \le \texttt{500}1≤s.length≤500
• s \texttt{s}s由小写英语字母组成

解法

思路和算法

为了确保相同字母最多出现在一个片段中，需要使用哈希表记录每个字母在字符串s ss中最后一次出现的下标。对于下标i ii处的字母c cc，将c cc最后一次出现的下标记为lastIndex \textit{lastIndex}lastIndex，则包含下标i ii的片段的结束下标一定大于等于lastIndex \textit{lastIndex}lastIndex，否则字母c cc会出现在多个片段中。在满足该条件的情况下，为了划分出尽可能多的片段，应使每个片段尽可能短，每个片段的结束下标尽可能小。这是一个贪心的策略。

得到每个字母在字符串s ss中最后一次出现的下标，从左到右遍历字符串s ss，遍历过程中维护当前片段的开始下标start \textit{start}start和结束下标end \textit{end}end。对于每个下标i ii，执行如下操作。

1. 记c = s [ i ] c = s[i]c=s[i]，得到字母c cc的最后一次出现的下标lastIndex \textit{lastIndex}lastIndex，则当前片段的结束下标一定大于等于lastIndex \textit{lastIndex}lastIndex，因此将end \textit{end}end更新为max ⁡ ( end , lastIndex ) \max(\textit{end}, \textit{lastIndex})max(end,lastIndex)。

2. 如果i = end i = \textit{end}i=end，则当前下标i ii为当前片段的结束下标，当前片段的下标范围是[ start , end ] [\textit{start}, \textit{end}][start,end]，当前片段的长度是end − start + 1 \textit{end} - \textit{start} + 1end−start+1，将当前片段的长度添加到结果列表中，然后将start \textit{start}start和end \textit{end}end都更新为i + 1 i + 1i+1，表示当前片段遍历结束，如果有下一个字母则下标i + 1 i + 1i+1为下一个片段的开始下标。

遍历结束之后，结果列表包含划分出的所有片段的长度。

上述贪心策略的正确性说明如下。

1. 对于遍历到的每个字母，都将当前片段的下标范围扩展到包含当前字母的最后一次出现的下标，因此每个片段不可能更短，否则当前字母会出现在多个片段中。

2. 遍历过程中遇到i = end i = \textit{end}i=end时，使用贪心策略，将i ii作为当前片段的结束下标，当i ii尚未到达字符串末尾时，将下标i + 1 i + 1i+1作为下一个片段的开始。如果不使用贪心策略，则不将下标i ii作为当前片段的结束下标，下一个片段的开始下标一定大于i + 1 i + 1i+1，字符串剩余部分的长度更少，因此不使用贪心策略可以划分出的片段数量不可能超过使用贪心策略可以划分出的片段数量。

代码

classSolution{publicList<Integer>partitionLabels(Strings){int[]lastIndices=newint[26];Arrays.fill(lastIndices,-1);intlength=s.length();for(inti=0;i<length;i++){charc=s.charAt(i);intindex=c-'a';lastIndices[index]=i;}List<Integer>partition=newArrayList<Integer>();intstart=0,end=0;for(inti=0;i<length;i++){charc=s.charAt(i);end=Math.max(end,lastIndices[c-'a']);if(i==end){partition.add(end-start+1);start=i+1;end=i+1;}}returnpartition;}}

复杂度分析

• 时间复杂度：O ( n ) O(n)O(n)，其中n nn是字符串s ss的长度。需要遍历字符串一次记录每个字母在字符串中最后一次出现的下标，然后需要遍历字符串一次计算划分结果。

• 空间复杂度：O ( ∣ Σ ∣ ) O(|\Sigma|)O(∣Σ∣)，其中Σ \SigmaΣ是字符集，这道题中Σ \SigmaΣ是全部小写英语字母，∣ Σ ∣ = 26 |\Sigma| = 26∣Σ∣=26。空间复杂度主要取决于哈希表，需要使用哈希表记录每个字母在字符串中最后一次出现的下标。注意返回值不计入空间复杂度。