# Leetcode 763. Partition Labels
###### tags: `Leetcode`

題目

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.先把每個字母的最後一個位置記起來到A陣列，至這邊需消耗O(N)

2.接著從頭開始，對於當下的字母去A陣列裡面找他最後出現的位置(last)，表示當下這個區間至少要到那個位置，接下來繼續做直到當下位置跟last位置相等，表示這個區間內的字母最多就只到這邊，就可以切割了

3.重複第2個步驟直到s[i]==0(因為結尾是'\0' ascii值就是0

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* partitionLabels(char * s, int* returnSize){
    int word[26] = {0};//表示26個字母出現的最後一個位置
    *returnSize = 0;
    for(int i = 0 ; s[i] != 0; i++)
    {
        word[s[i]-'a'] = i;
    }
    int start = 0;
    int last = 0;
    int *res = malloc(sizeof(int)*26);
    for(int i = 0 ; s[i] != 0; i++)
    {
        if(last < word[s[i]-'a'])
            last = word[s[i]-'a'];
        if(i == last)
        {
            res[*returnSize] = last - start + 1;
            (*returnSize)++;
            start = last+1;
        }
            
    }
    return res;
}