763 Partition Labels

# 1. Question

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:
1
2
3
Output: [9,7,8]
4
5
Explanation:
6
7
The partition is "ababcbaca", "defegde", "hijhklij".
8
This is a partition so that each letter appears in at most one part.
9
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.
Copied!
Note:
1. 1.
`S`will have length in range`[1, 500]`.
2. 2.
`S`will consist of lowercase letters (`'a'`to`'z'`) only.

# 2. Implementation

(1) Two Pointers
1
class Solution {
2
public List<Integer> partitionLabels(String S) {
3
List<Integer> res = new ArrayList<>();
4
5
if (S == null || S.length() == 0) {
6
return res;
7
}
8
9
// map记录s中的character最后出现的index
10
int[] map = new int;
11
for (int i = 0; i < S.length(); i++) {
12
map[S.charAt(i) - 'a'] = i;
13
}
14
15
int last = 0, start = 0;
16
17
for (int i = 0; i < S.length(); i++) {
18
last = Math.max(last, map[S.charAt(i) - 'a']);
19
20
if (last == i) {
21
22
start = i + 1;
23
}
24
}
25
return res;
26
}
27
}
Copied!

# 3. Time & Space Complexity

Two Pointers: 时间复杂度O(n), 空间复杂度O(n)