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) =
ababcbacadefegdehijhklijReturns (int)
3Example 2
Input
text (string) =
eccbbbbdecReturns (int)
1Example 3
Input
text (string) =
abcReturns (int)
3First 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 partitionsReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run