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

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

Пример:

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

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

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

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

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

😎 Решение:

function partitionLabels($s) {
    $lastPos = [];
    for ($i = 0; $i < strlen($s); $i++) {
        $lastPos[$s[$i]] = $i;
    }
    
    $partitions = [];
    $j = 0;
    $anchor = 0;
    for ($i = 0; $i < strlen($s); $i++) {
        $j = max($j, $lastPos[$s[$i]]);
        if ($i == $j) {
            $partitions[] = $i - $anchor + 1;
            $anchor = $i + 1;
        }
    }
    return $partitions;
}

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