763. Partition Labels

Задача

Вам дана строка s. Мы хотим разбить строку на как можно больше частей так, чтобы каждая буква встречалась не более чем в одной части. Например, строку "ababcbacadefegdehijhklij" можно разбить на ["ababcbaca", "defegde", "hijhklij"], но разбиения вида ["aba", "bcc"] или ["ab", "ab", "cc"] являются недопустимыми.

Обратите внимание, что разбиение выполняется так, чтобы после конкатенации всех частей по порядку получилась исходная строка s.

Верните список целых чисел, представляющих размеры этих частей.

Примеры

Пример 1

Input: s = "ababcbacadefegdehijhklij"
Output: [9,7,8]

Пояснение

Разбиение: “ababcbaca”, “defegde”, “hijhklij” — каждая буква попадает не более чем в одну часть.

Пример 2

Input: s = "eccbbbbdec"
Output: [10]

Решение

Решение

/**
 * Временная сложность: O(N) 
 * - Проходим по строке дважды (2 * N).
 * 
 * Пространственная сложность: O(1) 
 * - Храним map для 26 букв (константный размер, не зависит от N).
 */
var partitionLabels = function(s) {
    const lastIndices = {};
 
    // 1. Запоминаем последнее вхождение каждой буквы
    for (let i = 0; i < s.length; i++) {
        lastIndices[s[i]] = i;
    }
 
    const result = [];
    let end = 0;
    let size = 0;
 
    // 2. Жадный проход
    for (let i = 0; i < s.length; i++) {
        size += 1;
 
        // Расширяем границу текущего куска, если текущая буква встречается дальше
        end = Math.max(end, lastIndices[s[i]]);
 
        // Если дошли до границы куска — отрезаем
        if (i === end) {
            result.push(size);
            size = 0;
        }
    }
 
    return result;
};