[Leetcode][763. Partition Labels] The Illustration of Greedy Solution with Easy Detailed Explanation

By Long Luo

This article is the solution of Problem 763. Partition Labels.

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
763. Partition Labels

Medium

You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.

Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.

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.

Example 2:
Input: s = "eccbbbbdec"
Output: [10]

Constraints:
1 <= s.length <= 500
s consists of lowercase English letters.

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.

maxPosition

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
37
public 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)O(n), we will traversal the string twice.
  • Space Complexity: O(Σ)O(|\Sigma|),the Σ=26\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. 😉😃💗