# 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.