Medium

题目描述

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

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

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

示例 1：

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

示例 2：

输入：s = "eccbbbbdec"
输出：[10]

提示：

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

解题思路

这道题可以用贪心算法来解决。核心思想是：要使每个字母最多只出现在一个片段中，那么每个片段必须包含该片段内所有字母的完整出现范围。

解题思路：

  1. 记录每个字母最后出现的位置：遍历字符串，用哈希表记录每个字母最后一次出现的索引位置。

  2. 贪心划分：再次遍历字符串，维护当前片段的结束位置。对于当前位置的字母，如果它的最后出现位置超出了当前片段的结束位置，就需要扩展当前片段的范围。

  3. 确定片段边界：当遍历到当前片段的结束位置时，说明找到了一个完整的片段，此时可以进行划分。

算法流程：

  • 用数组或哈希表记录每个字母的最后出现位置
  • 遍历字符串，维护当前片段的起始和结束位置
  • 当到达片段结束位置时，记录该片段长度并开始新片段

这种贪心策略是正确的，因为我们总是选择最早可能的划分点，确保每个字母都完整地包含在某个片段中。

时间复杂度为 O(n)，空间复杂度为 O(1)（只需要存储26个字母的位置）。

代码实现

class Solution {
public:
    vector<int> partitionLabels(string s) {
        // 记录每个字母最后出现的位置
        vector<int> last(26);
        for (int i = 0; i < s.length(); i++) {
            last[s[i] - 'a'] = i;
        }
        
        vector<int> result;
        int start = 0, end = 0;
        
        for (int i = 0; i < s.length(); i++) {
            // 扩展当前片段的结束位置
            end = max(end, last[s[i] - 'a']);
            
            // 如果到达了当前片段的结束位置，进行划分
            if (i == end) {
                result.push_back(end - start + 1);
                start = i + 1;
            }
        }
        
        return result;
    }
};

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        # 记录每个字母最后出现的位置
        last = {}
        for i, char in enumerate(s):
            last[char] = i
        
        result = []
        start = 0
        end = 0
        
        for i, char in enumerate(s):
            # 扩展当前片段的结束位置
            end = max(end, last[char])
            
            # 如果到达了当前片段的结束位置，进行划分
            if i == end:
                result.append(end - start + 1)
                start = i + 1
        
        return result

public class Solution {
    public IList<int> PartitionLabels(string s) {
        // 记录每个字母最后出现的位置
        int[] last = new int[26];
        for (int i = 0; i < s.Length; i++) {
            last[s[i] - 'a'] = i;
        }
        
        List<int> result = new List<int>();
        int start = 0, end = 0;
        
        for (int i = 0; i < s.Length; i++) {
            // 扩展当前片段的结束位置
            end = Math.Max(end, last[s[i] - 'a']);
            
            // 如果到达了当前片段的结束位置，进行划分
            if (i == end) {
                result.Add(end - start + 1);
                start = i + 1;
            }
        }
        
        return result;
    }
}

var partitionLabels = function(s) {
    const lastIndex = {};
    for (let i = 0; i < s.length; i++) {
        lastIndex[s[i]] = i;
    }
    
    const result = [];
    let start = 0;
    let end = 0;
    
    for (let i = 0; i < s.length; i++) {
        end = Math.max(end, lastIndex[s[i]]);
        
        if (i === end) {
            result.push(end - start + 1);
            start = i + 1;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历字符串两次，第一次记录每个字母的最后位置，第二次进行划分
空间复杂度O(1)只需要常数空间存储26个字母的最后位置（不考虑结果数组）

相关题目