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

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

Пример:

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

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

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

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

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

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public IList<int> PartitionLabels(string s) {
        int[] lastPos = new int[26];
        for (int i = 0; i < s.Length; i++) {
            lastPos[s[i] - 'a'] = i;
        }
        
        List<int> partitions = new List<int>();
        int j = 0, anchor = 0;
        for (int i = 0; i < s.Length; i++) {
            j = Math.Max(j, lastPos[s[i] - 'a']);
            if (i == j) {
                partitions.Add(i - anchor + 1);
                anchor = i + 1;
            }
        }
        return partitions;
    }
}

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