LeetCode 763. Partition Labels (javascript)

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.

Example 1:

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.

Note:

S will have length in range [1, 500].
S will consist of lowercase English letters ('a' to 'z') only.

Idea:

Create hash table to track the last index of the letter
use start and end variable to decide the partition letters
when end reach to the last index of the letter :
- store the length of the partition letters (end – start + 1)
- reset start => end + 1

Solution:

/**
 * @param {string} S
 * @return {number[]}
 */
var partitionLabels = function(S) {
    let last_index = new Map();
    for (let i = 0; i < S.length; i++) {
        last_index.set(S[i],  i);
    }
    let res = [];
    let start = 0;
    let end = 0;
    for (let i = 0; i < S.length; i++) {
        end = Math.max(end, last_index.get(S[i]));
        if (i === end) {
            res.push(end - start + 1);
            start = end + 1;
        }
    }
    return res;
};