05 August 2008
给你一个字符串 s。我们希望将字符串划分为尽可能多的部分，以便每个字母最多出现在一个部分中。
请注意，分区已完成，以便在按顺序连接所有部分后，结果字符串应为 s。
返回表示这些部分大小的整数列表。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public List<Integer> partitionLabels(String s) {
int prev = -1;
List<Integer> results = new ArrayList<>();
Map<Character, Integer> mp = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
mp.put(s.charAt(i), i); //get last index of every element
}
int i = 0;
while (i < s.length()) {
int val = mp.get(s.charAt(i));
int max = val;
for (int j = i; j <= max; j++) {
max = Math.max(max, mp.get(s.charAt(j))); //update max with last occurence of any element
}
results.add(max - prev);
prev = max;
i = max + 1;
}
return results;
}
}