PROBLEM DESCRIPTION
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.
SOLUTION
Create a HashMap to store the start and end index of each character in the string. The start and end index of the first character will form the starting window size. However, this may need to be extended if any character within this window out of the window. So, we can iterate through this windows, and update the right side (end) of the window on the basis of lastIndex. This is the minimum window needed. The next window will start from R+1. Using the same logic, we check the minimum size of that window.
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class Solution {
public List<Integer> partitionLabels(String s) {
//HashMap to store first and last occurance of all characters in the string
Map<Character, Pair> map = new HashMap<>();
for(int i=0; i<s.length(); i++){
Character c = s.charAt(i);
if(!map.containsKey(c)){
map.put(c, new Pair(i, i));
}else{
map.put(c, new Pair(map.get(c).startIndex, i));
}
}
//init
int idx = 0;
//window start and end
int l=0;
int r=0;
//answer list
List<Integer> ans = new ArrayList<>();
//go through all the characters in the string
while(idx < s.length()){
//init -> window size as startIndex to endIndex of the left most element
l = map.get(s.charAt(idx)).startIndex;
r = map.get(s.charAt(idx)).endIndex;
//there can be a character in this window which is out of the window
//in that case, we need to update the right of the window
//temp int to store the right most index
int t = l;
while(t <= r && t < s.length()){
//update end of the window if it's beyong the current window
r = Math.max(r, map.get(s.charAt(t)).endIndex);
//check the next character
t++;
}
//next window will start from R+1
idx = r+1;
//add the size to the answer list
ans.add(r-l+1);
}
return ans;
}
}
class Pair{
int startIndex;
int endIndex;
public Pair(int s, int e){
this.startIndex = s;
this.endIndex = e;
}
}