https://leetcode.com/problems/partition-labels/
题意是要对一个字符串进行尽可能多的划分，并保证每个划分中的元素不在其他划分中出现。
想法比较具有技巧性。如果一段序列中每个元素的在S中最右边的序号都在某个范围内，那么就可以划分成一个段。
因此，使用字典保存每个元素出现的最靠右的位置。然后对字符串S进行遍历，找出最靠右的序号的最大值j。如果i和j重合了，说明已经到了这个划分的末尾了，然后进行划分。并开始计算下一个划分。
https://zxi.mytechroad.com/blog/string/leetcode-763-partition-labels/
https://segmentfault.com/a/1190000017354158
A string
S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.
Example 1:
Input: S = "ababcbacadefegdehijhklij" Output: [9,7,8] Explanation: The partition is "ababcbaca", "defegde", "hijhklij". This is a partition so that each letter appears in at most one part. A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.
Note:
Swill have length in range[1, 500].Swill consist of lowercase letters ('a'to'z') only
- 字符串中等題。滑動窗口+貪心。時間複雜度O(N)，空間複雜度O(N)。
- 首先依然是做hash，不過這次是對所有char記錄它們最後出現的位置。
- 然後定義三個指針，window開始left和結束right，當前i。每次移動i，然後判斷當前S[i]最後出現的位置是否大於當前right，如果是，則擴展right為last[S[i]]。
- 如果當前i == window結束right，則代表當前window中所有的字符都只在當前window中出現。所以可以把當前window的size記錄。同時移動left到下一個window的起點。
16 vector<int> partitionLabels(string S) { 17 vector<int> vResult; 18 19 // corner case 20 if (S.empty()) return vResult; 21 22 unordered_map<char, int> last; 23 24 // the last occurred index of S[i] 25 for (int i = 0; i < S.size(); ++ i) 26 last[S.at(i)] = i; 27 28 // start and end of the current window 29 int left = 0, right = 0; 30 31 // current pointer 32 for (int i = 0; i < S.size(); ++ i) { 33 right = max(right, last[S.at(i)]); // maximum index of the current window 34 35 // reach the end of current window 36 if (i == right) { 37 vResult.push_back(right - left + 1); // size of the current window 38 left = i + 1; // move to start of the next window 39 } 40 } 41 42 return vResult; 43 }https://blog.csdn.net/fuxuemingzhu/article/details/79265829
题意是要对一个字符串进行尽可能多的划分，并保证每个划分中的元素不在其他划分中出现。
想法比较具有技巧性。如果一段序列中每个元素的在S中最右边的序号都在某个范围内，那么就可以划分成一个段。
因此，使用字典保存每个元素出现的最靠右的位置。然后对字符串S进行遍历，找出最靠右的序号的最大值j。如果i和j重合了，说明已经到了这个划分的末尾了，然后进行划分。并开始计算下一个划分。
vector<int>
partitionLabels(string S) {
map<char, int> d;
for (int i = 0; i < S.size(); i++) d[S[i]] = i;
int start = 0, end = 0;
vector<int> res;
for (int i = 0; i < S.size(); i++) {
end = max(end, d[S[i]]);
if (i == end) {
res.push_back(end - start + 1);
start = end + 1;
}
}
return res;
}
http://www.cnblogs.com/grandyang/p/8654822.html
这道题给了我们一个字符串S，然我们将其尽可能多的分割为子字符串，条件是每种字符最多只能出现在一个子串中。比如题目汇总的例子，字符串S中有多个a，这些a必须只能在第一个子串中，再比如所有的字母e值出现在了第二个子串中。那么这道题的难点就是如何找到字符串的断点，即拆分成为子串的位置。我们仔细观察题目中的例子，可以发现一旦某个字母多次出现了，那么其最后一个出现位置必须要在当前子串中，字母a，e，和j，分别是三个子串中的结束字母。所以我们关注的是每个字母最后的出现位置，我们可以使用一个HashMap来建立字母和其最后出现位置之间的映射，那么对于题目中的例子来说，我们可以得到如下映射：
a -> 8
b -> 5
c -> 7
d -> 14
e -> 15
f -> 11
g -> 13
h -> 19
i -> 22
j -> 23
k -> 20
l -> 21
b -> 5
c -> 7
d -> 14
e -> 15
f -> 11
g -> 13
h -> 19
i -> 22
j -> 23
k -> 20
l -> 21
建立好映射之后，就需要开始遍历字符串S了，我们维护一个start变量，是当前子串的起始位置，还有一个last变量，是当前子串的结束位置，每当我们遍历到一个字母，我们需要在HashMap中提取出其最后一个位置，因为一旦当前子串包含了一个字母，其必须包含所有的相同字母，所以我们要不停的用当前字母的最后一个位置来更新last变量，只有当i和last相同了，即当i = 8时，当前子串包含了所有已出现过的字母的最后一个位置，即之后的字符串里不会有之前出现过的字母了，此时就应该是断开的位置，我们将长度9加入结果res中
https://leetcode.com/articles/partition-labels/
Let's try to repeatedly choose the smallest left-justified partition. Consider the first label, say it's
'a'. The first partition must include it, and also the last occurrence of 'a'. However, between those two occurrences of 'a', there could be other labels that make the minimum size of this partition bigger. For example, in "abccaddbeffe", the minimum first partition is "abccaddb". This gives us the idea for the algorithm: For each letter encountered, process the last occurrence of that letter, extending the current partition [anchor, j] appropriately.
Algorithm
We need an array
last[char] -> index of S where char occurs last. Then, let anchor and j be the start and end of the current partition. If we are at a label that occurs last at some index after j, we'll extend the partition j = last[c]. If we are at the end of the partition (i == j) then we'll append a partition size to our answer, and set the start of our new partition to i+1.
public List<Integer> partitionLabels(String S) {
int[] last = new int[26];
for (int i = 0; i < S.length(); ++i)
last[S.charAt(i) - 'a'] = i;
int j = 0, anchor = 0;
List<Integer> ans = new ArrayList();
for (int i = 0; i < S.length(); ++i) {
j = Math.max(j, last[S.charAt(i) - 'a']);
if (i == j) {
ans.add(i - anchor + 1);
anchor = i + 1;
}
}
return ans;
}
https://zxi.mytechroad.com/blog/string/leetcode-763-partition-labels/
public List<Integer> partitionLabels(String S) {
int lastIndex[] = new int[128];
for (int i = 0; i < S.length(); ++i)
lastIndex[(int)S.charAt(i)] = i;
List<Integer> ans = new ArrayList<>();
int start = 0;
int end = 0;
for (int i = 0; i < S.length(); ++i) {
end = Math.max(end, lastIndex[(int)S.charAt(i)]);
if (i == end) {
ans.add(end - start + 1);
start = end + 1;
}
}
return ans;
}
https://segmentfault.com/a/1190000017354158
