[LeetCode][763. Partition Labels] Greedy Solution with Easy Detailed Explanation
By Long Luo
This article is the solution Greedy Solution with Easy Detailed Explanation of Problem 763. Partition Labels .
Greedy
If we want to partition, we must maintain Two Pointers at the beginning and the end of a section. The Next Partition will start at the end of last Partition.
While scanning the string, if all the characters in the Partition only appear in the Partition, we can Partition it.
As the picture below shows, the farthest position of all the chars is no more than \(8\), so we can partition it.
and so on.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37public static List<Integer> partitionLabels(String s) {
List<Integer> ans = new ArrayList<>();
if (s.length() <= 1) {
ans.add(s.length());
return ans;
}
int len = s.length();
Map<Character, Integer> idxMap = new HashMap<>();
for (int i = 0; i < len; i++) {
char ch = s.charAt(i);
if (idxMap.containsKey(ch)) {
idxMap.put(ch, i);
} else {
idxMap.put(ch, i);
}
}
int index = 0;
int[] partSection = new int[2];
while (index < len) {
while (index >= partSection[0] && index <= partSection[1]) {
char ch = s.charAt(index);
index++;
int lastIdx = idxMap.get(ch);
if (lastIdx > partSection[1]) {
partSection[1] = lastIdx;
}
}
ans.add(partSection[1] - partSection[0] + 1);
partSection[0] = partSection[1] = index;
}
return ans;
}
Analysis
- Time Complexity: \(O(n)\) , we will traversal the string twice.
- Space Complexity: \(O(|\Sigma|)\) ，the \(\Sigma = 26\).
All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions . 😉😃💗