划分字母区间

Leetcode题目链接

描述

详见中文题目链接。

解答

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int last[26];
        int len = s.size();
        for (int i = 0; i < len; i++) last[s[i] - 'a'] = i;

        vector<int> partition;
        int start = 0, end = 0;
        for (int i = 0; i < len; i++) {
            end = max(end, last[s[i] - 'a']);
            if (i == end) {
                partition.emplace_back(end - start + 1);
                start = end = i + 1;
            }
        }
        return partition;
    }
};