###### tags: `LeetCode` `string`

# 0763. Partition Labels (Medium)
耗時：19 分鐘

## 題目
You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.

Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.

Return a list of integers representing the size of these parts.

## 思路
1. 子字串中的所有字母都已經位於該子字串，舉例來說："ababcbacadefegde"中，讀到"ababcbaca"的時候，所有的'a', 'b', 'c'皆已位於此子串內，因此這個子字串就可以直接分離出去。

* Time Complexity：O(26 * n) = O(n)
* Space Complexity：O(n)

### 程式碼

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int cnt[26] = {0};
        int part_cnt = 0;
        
        bool substr_contains[26] = {false};
        bool _compelete_output;
        
        vector<char> set_substring;
        vector<int> ans;
        
        for (int i = 0; i < s.length(); ++i) {
            ++cnt[s[i] - 'a'];
        }
        
        for (int i = 0; i < s.length(); ++i) { 
            _compelete_output = true;
            substr_contains[s[i] - 'a'] = true;
            --cnt[s[i] - 'a'];
            ++part_cnt;
            
            for (int j = 0; j < 26; ++j) {
                if (substr_contains[j])
                    if (cnt[j] != 0) {
                        _compelete_output = false;
                        break;
                    }
            }

            if (_compelete_output || i == s.length() - 1) {
                ans.push_back(part_cnt);
                part_cnt = 0;
            }
        }
        
        return ans;
    }
};