763 Partition Labels

1. Question

A stringSof 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
Input: S = "ababcbacadefegdehijhklij"
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.
    Swill have length in range[1, 500].
  2. 2.
    Swill 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[26];
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
res.add(last - start + 1);
22
start = i + 1;
23
}
24
}
25
return res;
26
}
27
}
Copied!

3. Time & Space Complexity

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