跳转至

763 划分字母区间

对于划分区间问题,我们通常会想到贪心

做法通常是比较区间的末端,更新区间

在本题中,分析题目:

  • 同一字母最多出现在一个片段中 -> 假设字母出现的最后位置\(end_c\)为last[s[i] - 'a'],区间末端\(end\)必须要大于等于\(end_c\),否则会出现两个字母出现在不同片段
  • 把这个字符串划分为尽可能多的片段 -> 只要满足i到达区间末端\(end\),说明当前区间[start, end]所有字母出现的最后位置\(end_c\)为last[s[i] - 'a'],都满足\(end_c\)小于等于区间末端\(end\),那么我们就可以立即划分区间,从而得到尽可能多的区间
class Solution {
public:
    vector<int> partitionLabels(string s) {
        int n = s.size();
        int last[26];
        vector<int> res;
        // 统计每个字符最后出现的下标
        for(int i = 0; i < n; i++){
            last[s[i] - 'a'] = i;
        }
        // start为区间开始点,end为区间结束点
        // end一定为某区间内所有last[j]的最大值
        int start = 0, end = 0;
        for(int i = 0; i < n; i++){
            end = max(end, last[s[i] - 'a']);
            // i == end 说明区间终点end已确定 且已遍历到区间终点end
            if(i == end){
                res.push_back(end - start + 1);
                start = end + 1;
            }
        }
        return res;
    }
};

复杂度分析

时间复杂度:O(n),其中 n 是字符串的长度。需要遍历字符串两次,第一次遍历时记录每个字母最后一次出现的下标位置,第二次遍历时进行字符串的划分。

空间复杂度:O(∣Σ∣),其中 Σ 是字符串中的字符集。这道题中,字符串只包含小写字母,因此 ∣Σ∣=26。