763. 划分字母区间

763. 划分字母区间

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

示例：

输入：S = “ababcbacadefegdehijhklij”
输出：[9,7,8]
解释：
划分结果为 “ababcbaca”, “defegde”, “hijhklij”。
每个字母最多出现在一个片段中。
像 “ababcbacadefegde”, “hijhklij” 的划分是错误的，因为划分的片段数较少。

这题我们可以使用两个辅助数组，可以很好的解决问题：

/** * Note: The returned array must be malloced, assume caller calls free(). */
int* partitionLabels(char * s, int* returnSize){
    
    int r[26];
     int r_t[26];
    int i;
    int *re=(int *)malloc(sizeof(int)*26);
    for(i=0;i<26;i++){
    
        r[i]=0;
        r_t[i]=0;
    }
    i=0;
    while(s[i]!='\0'){
    
        r[s[i]-'a']++;
        i++;
    }
    int sum=0;
    int now=-1;
    i=0;
    int size=0;
    while(s[i]!='\0'){
    
          r_t[s[i]-'a']++;
          sum++;
        if( r_t[s[i]-'a']==r[s[i]-'a']){
    
            sum=sum-r[s[i]-'a'];
            if(sum==0){
    
                re[size++]=i-now;
                now=i;
            }
        }
        i++;
       
    }
    *returnSize=size;
    return re;

}