題目： LeetCode - 763. Partition Labels

題目說明

給一個只包含小寫英文字母的字串 S，求依照題目的要求分割的子串的長度。題目要求子串中若出現某個字母，則此子串須包含字串中的所有此字母，並且需切割出最多的子串。

解題思路

使用一個陣列紀錄每個字母最後出現的 index，定義兩個整數 l, r，接著遍歷字串，r 每次更新為 r 及 lastIdx[S[i] - 'a'] 兩者的最大值，這樣可以確保此子串能包含所有出現過的字母，若是 i == r 表示已經可以切割了，長度及為 r - l + 1，接著更新 l 即可。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> partitionLabels(string S) {
        int n = S.size(), l = 0, r = 0;
        vector<int> v, lastIdx(26);
        for(int i = 0; i < n; ++i) lastIdx[S[i] - 'a'] = i;
        for(int i = 0; i < n; ++i)
        {
            r = max(r, lastIdx[S[i] - 'a']);
            if(i == r) v.emplace_back(r - l + 1), l = ++r;
        }
        return v;
    }
};