Array Sorting Greedy
Intermediate Level

Implement the partitionLabelsNumber method that returns how many partitions can be made so each character appears in one part.

The input is a string text.

Your task is to split the string into the maximum number of partitions so that each character appears in at most one partition. Return only the number of partitions.

For example, ababcbacadefegdehijhklij can be split into three valid parts, so the answer is 3.

Example 1
Input:
text (string) = ababcbacadefegdehijhklij
Return:
(int) 3
Example 2
Input:
text (string) = eccbbbbdec
Return:
(int) 1
Example 3
Input:
text (string) = abc
Return:
(int) 3

First record the last index where each character appears.

Then scan the string and keep the farthest last occurrence of all characters seen in the current partition. When the current index reaches that farthest boundary, the partition can end safely because every character in it is complete.

Count every completed partition and return the count.

Pseudocode:

function partitionLabelsNumber(text):
    last = map from character to last index
    for i from 0 to length(text) - 1:
        last[text[i]] = i
    partitions = 0
    end = 0
    for i from 0 to length(text) - 1:
        end = max(end, last[text[i]])
        if i == end:
            partitions++
    return partitions
Run your code to see the result.