Swift | LeetCode

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

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

👨‍💻 Алгоритм: 1⃣Создайте словарь для хранения последней позиции каждой буквы в строке. 2⃣Пройдите по строке, отслеживая максимальную позицию текущей части. 3⃣Когда текущая позиция совпадает с максимальной позицией, завершите часть и начните новую. 😎 Решение:

func partitionLabels(_ s: String) -> [Int] {
    var lastPos = [Character: Int]()
    for (idx, char) in s.enumerated() {
        lastPos[char] = idx
    }
    
    var partitions = [Int]()
    var j = 0, anchor = 0
    for (i, char) in s.enumerated() {
        j = max(j, lastPos[char]!)
        if i == j {
            partitions.append(i - anchor + 1)
            anchor = i + 1
        }
    }
    return partitions
}

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