Leetcode 763 - Partition labels

Note:

• 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

Brute force

Greedy Optimal