Leetcode #763 Partition Labels

A string S of lowercase English 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.

Input s = “ababcbacadefegdehijhklij”;

Output = [9, 7, 8]

The parts are : “ababcbaca”, “defegde”, “hijhklij”.

To solve this problem, we need to find the last index of every character. For example, the last index of ‘a’ is 8. We store those values in a map. When we traverse through the string, as soon as we arrive at the maximum index possible for a given substring, we add that length to the list.

public List<Integer> partitionLabels(String S) {
Map<Character, Integer> map = new HashMap<>();
// Store the last index of every character
for(int i = 0; i < S.length(); i++) {
char ch = S.charAt(i);
map.put(ch, i);
}
int max = 0;
List<Integer> result = new ArrayList<>();
int start = 0;
for(int i = 0; i < S.length(); i++) {
char ch = S.charAt(i);
int index = map.get(ch);
max = Math.max(index, max);
// we evaluate the maximum possible index of the current substring
if(max == i) {
int len = max - start + 1;
result.add(len);
start = i + 1;
}
}
return result;
}

Time complexity of the solution = O(n), where n is the total number of elements.