題目網址：https://leetcode.cn/problems/partition-labels/

題意：給一 string s 由小寫字母所組成。我們要把 s 劃分為盡可能多的 partition, 同一字母只能出現在同一個 partition 中。返回一個表示每個 partition 的長度之 array。

Solution：

想法：利用 Greedy, 首先遍歷 s, 並用 lastIdx 紀錄每個字母的最後一個 index, 然後從頭開始遍歷 s, 並不斷更新當前 partition 的結尾。若 i == idx 代表已走到 partition 結尾, 即可確定當前 partition 的 size, 因為該 partition 中的 char 都沒有出現在更後面的位置

class Solution {
public:
    vector<int> partitionLabels(string s) {
        const int n = s.size();
        unordered_map<char, int> lastIdx; // {char, last index}

        for (int i = 0; i < n; ++i) {
            lastIdx[s[i]] = i;
        }

        vector<int> res;
        int curSize = 0, end = 0;

        for (int i = 0; i < n; ++i) {
            ++curSize;
            end = max(end, lastIdx[s[i]]); // 更新當前 partition 的結尾

            // 抵達該 partition 的結尾
            if (i == end) {
                res.emplace_back(curSize);
                curSize = 0; // 下一個 partition 的長度從 0 開始算
            }
        }

        return res;
    }
};
  • time：$O(n)$ ➔ for loop
  • space：$O(1)$ ➔ lastIdx 中的元素不超過 26 個