algo-aha

同一字母分在同一子段，最多能分多少段

• https://leetcode.com/problems/partition-labels/

每个字母都向右扩展当前区间右端点，右端点不再扩展时子段结束、区间数++

vector<int> partitionLabels(string S) {
    unordered_map<char, int> lastIdx;
    for (int i = 0; i < S.size(); i++) {
        lastIdx[S[i]] = i;
    }
    
    vector<int> ans;
    // 每个字母都向右扩展当前区间右端点
    int left = 0, right = -1;
    for (int i = 0; i < S.size(); i++) {
        right = max(right, lastIdx[S[i]]);
        if (i == right) { // 右端点不再扩展时子段结束
            ans.push_back(right - left + 1);
            left = right + 1;
        }
    }
    return ans;        
}