Сложность: 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
}Ставь 👍 и забирай 📚 Базу знаний