題目描述

給你一個字符串 s 。我們要把這個字符串劃分為盡可能多的片段，同一字母最多出現在一個片段中。
注意，劃分結果需要滿足：將所有劃分結果按順序連接，得到的字符串仍然是 s 。
返回一個表示每個字符串片段的長度的列表。

題目分析

1. 由于題目中規定同一字母最多出現在一個片段中，因此，需要找到字符串中出現的每個字母的最后一次出現的下標位置。對字符串進行一次遍歷即可得到，并存儲在數組last_pos中。
2. 然后可以使用貪心算法思想對字符串劃分出盡可能多的片段：
   • 從左至右依次訪問字符串元素，同時維護當前片段的開始下標start和結束下標end，初始時 start=end=0。
   • 對于每個被訪問到的字母char，從last_pos中獲取當前字母的最后一次出現的下標位置，如果其最后出現的位置大于當前片段邊界end，則更新end，否則不更新，來確保每個字母在同一個片段里。
   • 當訪問到下標等于當前片段邊界end時，當前片段訪問結束，當前片段的下標范圍是 [start,end]，長度為end?start+1，將當前片段的長度添加到返回值數組中，然后更新下一個片段的start=end+1，繼續處理下一個片段。
   • 重復上述過程，直到方問完字符串的全部元素。

Code

class Solution {
public:vector<int> partitionLabels(string s) {int last_pos[26];int len = s.size();for (int i = 0; i < len; ++i) {last_pos[s[i] - 'a'] = i;}vector<int> ans;int start = 0,end = 0;for (int i = 0; i < len; ++i) {if (end < last_pos[s[i] - 'a']) {end = last_pos[s[i] - 'a'];}if (end == i) {ans.emplace_back(end - start + 1);start = end + 1;}}return ans;}
};