763. 划分字母区间

763. 划分字母区间

• 统计每一个字符最后出现的位置
• 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

  class Solution {
  public:
    vector<int> partitionLabels(string s) {
        int hash[27] = {0};
        for(int i=0;i<s.size();i++)
        {
            hash[s[i]-'a']=i;
        }
        int left = 0;
        int right = 0;
        vector<int> result;
        for(int i =0;i<s.size();i++)
        {
            right = max(hash[s[i]-'a'],right);
            if(right == i)
            {
                result.push_back(right-left+1);
                left = i+1;
            }
        }
        return result;
    }
  };