No matter which method, we have to use Map to get each char’s [firstIndex, lastIndex]. So, we are actually dealing with question of merging intervals.

Because the result would be a sorted array, we need to sort by firstIndex.

If cur's firstIndex > prev's lastIndex, it means there is no overlap. Add cur as a new element.

If cur's firstIndex < prev's lastIndex, it means there is overlap. Don’t add cur and update prev's lastIndex to Math.max(intervals[i][1], result[result.length - 1][1]).

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.

Return a list of integers representing the size of these parts.

Example

1 2 3 4 5 6

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.