Задача: 763. Partition Labels
Сложность: medium

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

Пример:

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

👨‍💻 Алгоритм:

1⃣Создайте словарь для хранения последней позиции каждой буквы в строке.

2⃣Пройдите по строке, отслеживая максимальную позицию текущей части.

3⃣Когда текущая позиция совпадает с максимальной позицией, завершите часть и начните новую.

😎 Решение:

function partitionLabels(s) {
    const lastPos = new Map();

    for (let i = 0; i < s.length; i++) {
        lastPos.set(s[i], i);
    }

    const partitions = [];
    let j = 0, anchor = 0;

    for (let i = 0; i < s.length; i++) {
        j = Math.max(j, lastPos.get(s[i]));
        if (i === j) {
            partitions.push(i - anchor + 1);
            anchor = i + 1;
        }
    }

    return partitions;

Ставь 👍 и забирай 📚 Базу знаний