Python | LeetCode

Ведем набор учеников 3-10 классов на новый учебный год! Московская школа программистов - это не курсы, а школа с государственной лицензией, которая обучает детей IT с 2001 года. Мы сотрудничаем с МФТИ, НИУ ВШЭ, Яндекс и Физтехпарк Что получит ребенок, в результате обучения: - Участие и победы в олимпиадах всероссийского и международного уровня - Поступление в престижные технические вузы России и работу в известных IT-компаниях: Apple, Google, Yandex, Nvidia и других - Практику на реальных IT-проектах - Усидчивость, целеустремленность и умение работать в команде - Сдача ЕГЭ/ОГЭ на высокие баллы Сейчас идет набор в виртуальный класс. В этом формате, дети в небольших группах обучаются с преподавателем онлайн в реальном времени. Эффективно как очно. Позаботьтесь о том, чтобы ребенок стал востребованным IT-специалистом! Зарегистрироваться #реклама 16+ vc.informatics.ru О рекламодателе

Задача: 1253. Reconstruct a 2-Row Binary Matrix Сложность: medium Даны следующие сведения о матрице с n столбцами и 2 строками: Матрица является двоичной, то есть каждый элемент матрицы может быть 0 или 1. Сумма элементов 0-й (верхней) строки задана как upper. Сумма элементов 1-й (нижней) строки задана как lower. Сумма элементов i-го столбца (индексированного 0) - colsum[i], где colsum - целочисленный массив длины n. Ваша задача - восстановить матрицу с upper, lower и colsum. Вернуть ее в виде двумерного целочисленного массива. Если существует более одного правильного решения, будет принято любое из них. Если правильного решения не существует, верните пустой двумерный массив. Пример:

Input: upper = 2, lower = 1, colsum = [1,1,1]
Output: [[1,1,0],[0,0,1]]

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

def reconstructMatrix(upper, lower, colsum):
    n = len(colsum)
    top = [0] * n
    bottom = [0] * n
    
    for i in range(n):
        if colsum[i] == 2:
            if upper > 0 and lower > 0:
                top[i] = 1
                bottom[i] = 1
                upper -= 1
                lower -= 1
            else:
                return []
    
    for i in range(n):
        if colsum[i] == 1:
            if upper > lower:
                if upper > 0:
                    top[i] = 1
                    upper -= 1
                else:
                    return []
            else:
                if lower > 0:
                    bottom[i] = 1
                    lower -= 1
                else:
                    return []

    if upper == 0 and lower == 0:
        return [top, bottom]
    else:
        return []

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

Дарим подписку на Яндекс Музыку Ответьте на 1 вопрос и Яндекс Музыка ваша для вас и 3-х ваших близких. Кинопоиск и Яндекс Книги тоже в подписке. Попробуйте бесплатно❤️ Попробовать #реклама 18+ music.yandex.ru О рекламодателе Реклама на Яндексе

Задача: 233. Number of Digit One Сложность: hard Дано целое число n, посчитайте общее количество единиц, встречающихся во всех неотрицательных числах, меньших или равных n. Пример:

Input: n = 13
Output: 6

👨‍💻 Алгоритм: 1⃣Итерация по степеням 10: Итеративно увеличивайте значение i от 1 до n, увеличивая i в 10 раз на каждом шаге. Это позволяет анализировать каждую цифру числа n. 2⃣Подсчет групповых единиц: Для каждой итерации добавляйте (n / (i * 10)) * i к счетчику countr, что представляет собой количество единиц, встречающихся в группах размера i после каждого интервала (i * 10). 3⃣Добавление дополнительных единиц: Для каждой итерации добавляйте min(max((n % (i * 10)) - i + 1, 0), i) к счетчику countr, что представляет собой дополнительные единицы, зависящие от цифры на позиции i. 😎 Решение:

def countDigitOne(n: int) -> int:
    countr = 0
    i = 1
    while i <= n:
        divider = i * 10
        countr += (n // divider) * i + min(max(n % divider - i + 1, 0), i)
        i *= 10
    return countr

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

Регистрируйтесь на вебинар UserGate WAF 💻Расскажет как новая версия UserGate WAF поможет защитить ваши веб-приложения и какие обновления ждут вас в 2025 году ✅На вебинаре будет: - Преимущества и особенности UserGate WAF - Принципы работы и сценарии использования - Демонстрация возможностей WAF - Планы развития продукта в 2025 году - Ответы на вопросы 👌Расскажем, как защитить вашу компанию. Регистрируйтесь — будет интересно! Зарегистрироваться #реклама 16+ webinar.usergate.com О рекламодателе

Задача: 1376. Time Needed to Inform All Employees Сложность: medium В компании работает n сотрудников, каждому из которых присвоен уникальный идентификатор от 0 до n - 1. Руководитель компании имеет идентификатор headID. У каждого сотрудника есть один непосредственный начальник, указанный в массиве manager, где manager[i] — это непосредственный начальник i-го сотрудника, manager[headID] = -1. Также гарантируется, что отношения подчинения образуют древовидную структуру. Руководитель компании хочет сообщить всем сотрудникам компании срочную новость. Он сообщит своим непосредственным подчиненным, а они сообщат своим подчиненным и так далее, пока все сотрудники не узнают о срочной новости. i-й сотрудник нуждается в informTime[i] минутах, чтобы сообщить всем своим непосредственным подчиненным (т.е. через informTime[i] минут все его непосредственные подчиненные могут начать распространять новость). Верните количество минут, необходимых для того, чтобы сообщить всем сотрудникам о срочной новости. Пример:

Input: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
Output: 1
Explanation: The head of the company with id = 2 is the direct manager of all the employees in the company and needs 1 minute to inform them all.
The tree structure of the employees in the company is shown.

👨‍💻 Алгоритм: 1⃣Создайте список смежности adjList; индекс i будет хранить смежные узлы для сотрудника с идентификатором i. 2⃣Итерируйте по сотрудникам от 0 до N - 1, и для каждого сотрудника i добавляйте ребро manager[i] -> i, если manager[i] не равен -1. 3⃣Начните выполнение DFS с узла headID и временем 0 для каждого узла как curr. Обновите максимальное время maxTime, сравнив его с текущим временем. Итерируйте по смежным узлам curr и для каждого смежного узла выполните DFS с временем time + informTime[curr]. Когда DFS завершится, верните maxTime. 😎 Решение:

class Solution:
    def __init__(self):
        self.maxTime = float('-inf')
    
    def DFS(self, adjList, informTime, curr, time):
        self.maxTime = max(self.maxTime, time)
        for adjacent in adjList[curr]:
            self.DFS(adjList, informTime, adjacent, time + informTime[curr])
    
    def numOfMinutes(self, n, headID, manager, informTime):
        adjList = [[] for _ in range(n)]
        for i in range(n):
            if manager[i] != -1:
                adjList[manager[i]].append(i)
        self.DFS(adjList, informTime, headID, 0)
        return self.maxTime

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

Крупнейший университет искусственного интеллекта Приглашаем на бесплатный однодневный интенсив по AI! Освой искусственный интеллект для профессионального роста: создавай нейросети, автоматизируй бизнес-задачи и зарабатывай на AI-решениях. ✨ 8 000+ студентов со всего мира ✨ 600+ AI-проектов, созданных студентами ✨ Сборная Университета — победители крупнейших AI-хакатонов России ✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие) ✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие) Будем рады видеть тебя в наших рядах! Узнать больше #реклама 16+ neural-university.ru О рекламодателе

Задача: 352. Data Stream as Disjoint Intervals Сложность: hard Дано поступление данных из последовательности неотрицательных целых чисел a1, a2, ..., an, необходимо обобщить увиденные числа в виде списка непересекающихся интервалов. Реализуйте класс SummaryRanges: SummaryRanges() Инициализирует объект с пустым потоком. void addNum(int value) Добавляет целое число в поток. int[][] getIntervals() Возвращает обобщение текущих чисел в потоке в виде списка непересекающихся интервалов [starti, endi]. Ответ должен быть отсортирован по starti. Пример:

Input
["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"]
[[], [1], [], [3], [], [7], [], [2], [], [6], []]
Output
[null, null, [[1, 1]], null, [[1, 1], [3, 3]], null, [[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, [[1, 3], [6, 7]]]

👨‍💻 Алгоритм: 1⃣Инициализировать структуру данных TreeSet для хранения значений. 2⃣addNum(int value) Просто добавить value в values. Если эквивалент TreeSet вашего языка программирования позволяет дублировать значения, как например SortedList в Python, нужно также проверить, что value не существует в values, так как дубликаты нарушат алгоритм. 3⃣getIntervals Если values пуст, вернуть пустой массив. Создать пустой список интервалов. Установить left = right = -1. left представляет левую границу текущего интервала, а right представляет правую границу. Итерировать по values. На каждой итерации: Если left < 0, установить left = right = value. Иначе, если value = right + 1, установить right = value, так как мы можем продолжить текущий интервал. Иначе, мы не можем продолжить текущий интервал. Вставить [left, right] в intervals и установить left = right = value для начала нового интервала. Вставить [left, right] в intervals и вернуть intervals. 😎 Решение:

class SummaryRanges:
    def __init__(self):
        self.values = set()

    def addNum(self, value: int) -> None:
        self.values.add(value)

    def getIntervals(self) -> list[list[int]]:
        if not self.values:
            return []
        intervals = []
        sorted_values = sorted(self.values)
        left, right = -1, -1
        for value in sorted_values:
            if left < 0:
                left, right = value, value
            elif value == right + 1:
                right = value
            else:
                intervals.append([left, right])
                left, right = value, value
        intervals.append([left, right])
        return intervals

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

Крупнейший университет искусственного интеллекта Приглашаем на бесплатный курс по искусственному интеллекту! Мы подготовили для тебя 5 занятий по теме «Разработка нейро-сотрудников на GPT». Пройди регистрацию для получения полного бесплатного доступа к курсу. ✨ 8 000+ студентов со всего мира ✨ 600+ AI-проектов, созданных студентами ✨ Сборная Университета — победители крупнейших AI-хакатонов России ✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие) ✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие) Будем рады видеть тебя в наших рядах! Узнать больше #реклама 16+ neural-university.ru О рекламодателе

Задача: 104. Maximum Depth of Binary Tree Сложность: easy Дан корень бинарного дерева, верните его максимальную глубину. Максимальная глубина бинарного дерева — это количество узлов вдоль самого длинного пути от корневого узла до самого удалённого листового узла. Пример:

Input: root = [3,9,20,null,null,15,7]
Output: 3

👨‍💻 Алгоритм: 1️⃣Можно обойти дерево, используя стратегию поиска в глубину (DFS) или поиска в ширину (BFS). 2️⃣Для данной задачи подойдет несколько способов. 3️⃣Здесь мы демонстрируем решение, реализованное с использованием стратегии DFS и рекурсии. 😎 Решение:

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        else:
            left_height = self.maxDepth(root.left)
            right_height = self.maxDepth(root.right)
            return max(left_height, right_height) + 1

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

Получи грант на обучение в Центральном университете Центральный университет выдает гранты на 4 года обучения в бакалавриате. Грант покрывает до 100% стоимости обучения. Участвуй в отборе, чтобы получить грант. Получи доступ к уникальным активностям для абитуриентов. Для выпускников 10-х, 11-х классов и колледжей. Подать заявку #реклама apply.centraluniversity.ru О рекламодателе

Задача: 1463. Cherry Pickup II Сложность: hard Дана матрица grid размером rows x cols, представляющая поле с вишнями, где grid[i][j] обозначает количество вишен, которые можно собрать с клетки (i, j). У вас есть два робота, которые могут собирать вишни: Робот №1 находится в левом верхнем углу (0, 0), а Робот №2 находится в правом верхнем углу (0, cols - 1). Верните максимальное количество собранных вишен с помощью обоих роботов, следуя приведённым ниже правилам: Из клетки (i, j) роботы могут перемещаться в клетку (i + 1, j - 1), (i + 1, j) или (i + 1, j + 1). Когда любой робот проходит через клетку, он подбирает все вишни, и клетка становится пустой. Когда оба робота находятся в одной клетке, только один из них собирает вишни. Оба робота не могут выходить за пределы матрицы в любой момент времени. Оба робота должны достичь нижней строки в матрице grid. Пример:

Input: grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
Output: 28
Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (1 + 9 + 5 + 2) = 17.
Cherries taken by Robot #2, (1 + 3 + 4 + 3) = 11.
Total of cherries: 17 + 11 = 28.

👨‍💻 Алгоритм: 1⃣Определите трехмерный массив dp, где dp[row][col1][col2] представляет максимальное количество вишен, которые можно собрать, если робот 1 находится в (row, col1), а робот 2 находится в (row, col2). 2⃣Итеративно заполните dp, начиная с нижней строки, вычисляя для каждой клетки максимальное количество вишен, которое можно собрать с учетом возможных перемещений роботов. 3⃣Верните dp[0][0][n-1], что представляет максимальное количество вишен, которое можно собрать, начиная с верхнего левого и верхнего правого углов. 😎 Решение:

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[[0] * n for _ in range(n)] for _ in range(m)]
        
        for row in range(m - 1, -1, -1):
            for col1 in range(n):
                for col2 in range(n):
                    result = grid[row][col1]
                    if col1 != col2:
                        result += grid[row][col2]
                    if row != m - 1:
                        max_cherries = 0
                        for new_col1 in range(col1 - 1, col1 + 2):
                            for new_col2 in range(col2 - 1, col2 + 2):
                                if 0 <= new_col1 < n and 0 <= new_col2 < n:
                                    max_cherries = max(max_cherries, dp[row + 1][new_col1][new_col2])
                        result += max_cherries
                    dp[row][col1][col2] = result
        return dp[0][0][n - 1]

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

Профессия «Аналитик данных». Рассрочка 0% Освойте высокооплачиваемую IT-профессию с нуля за 6 месяцев. Выдаём диплом, помогаем с трудоустройством. Excel, SQL, PowerBI, Python. Преимущества обучения в Академии Eduson: 🎓 официальный государственный диплом 🎓если после курса не найдёте работу — мы возвращаем деньги и это зафиксировано в договоре 🎓 рассрочка 0% на 24 мес., то есть без переплаты 🎓 бессрочный доступ к лекциям и материалам, которые продолжают обновляться 🎓 личный куратор с Вами на связи Начните обучаться онлайн и получать стабильный доход уже во время обучения! Узнать больше Финансовые услуги оказывает: ПАО "Сбербанк", АО "Тинькофф Банк" и др.. #реклама 16+ eduson.academy О рекламодателе

Задача: 27. Remove Element Сложность: easy Учитывая целочисленный массив nums и целочисленное значение val, удалите все вхождения val в nums на месте. Порядок элементов может быть изменен. Затем верните количество элементов в виде чисел, которые не равны val. Учитывайте количество элементов в nums, которые не равны val как k. Чтобы вас приняли, вам необходимо сделать следующее: - Измените массив nums так, чтобы первые k элементов nums содержали элементы, не равные val. Остальные элементы nums не важны, как и размер nums. - Вернуть k. Пример:

Input: nums = [3,2,2,3], val = 3  
Output: 2, nums = [2,2,_,_]  

👨‍💻 Алгоритм: 1️⃣Инициализируем указатель k для отслеживания позиции уникальных элементов. 2️⃣Проходим по массиву, копируя элементы, которые не равны val, на место указателя k. 3️⃣Возвращаем k — количество элементов, не равных val. 😎 Решение:

class Solution:  
    def removeElement(self, nums: List[int], val: int) -> int:  
        k = 0  

        for i in range(len(nums)):  
            if nums[i] != val:  
                nums[k] = nums[i]  
                k += 1  

        return k

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

Профессия «Аналитик данных» - начни учиться бесплатно! Освойте высокооплачиваемую IT-профессию с нуля за 6 месяцев. Выдаём диплом, помогаем с трудоустройством. Excel, SQL, PowerBI, Python. Преимущества обучения в Академии Eduson: 🎓 можно начать учиться бесплатно, если не понравится — не платите 🎓 официальный государственный диплом 🎓 рассрочка 0% на 24 мес. 🎓 бессрочный доступ к лекциям и материалам, которые регулярно обновляются 🎓 личный куратор с Вами на связи Начните обучаться онлайн и получать стабильный доход уже во время обучения! Подать заявку #реклама 16+ eduson.academy О рекламодателе

Задача: 563. Binary Tree Tilt Сложность: easy Дано корневое значение бинарного дерева. Вернуть сумму значений наклонов всех узлов дерева. Наклон узла дерева - это абсолютная разница между суммой всех значений узлов левого поддерева и всех значений узлов правого поддерева. Если у узла нет левого потомка, то сумма значений узлов левого поддерева считается равной 0. То же правило применяется, если у узла нет правого потомка. Пример:

Input: root = [1,2,3]
Output: 1
Explanation: 
Tilt of node 2 : |0-0| = 0 (no children)
Tilt of node 3 : |0-0| = 0 (no children)
Tilt of node 1 : |2-3| = 1 (left subtree is just left child, so sum is 2; right subtree is just right child, so sum is 3)
Sum of every tilt : 0 + 0 + 1 = 1

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

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def findTilt(self, root: TreeNode) -> int:
        self.total_tilt = 0
        
        def sum_and_tilt(node):
            if not node:
                return 0
            left_sum = sum_and_tilt(node.left)
            right_sum = sum_and_tilt(node.right)
            node_tilt = abs(left_sum - right_sum)
            self.total_tilt += node_tilt
            return node.val + left_sum + right_sum
        
        sum_and_tilt(root)
        return self.total_tilt

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

Дарим подписку на Яндекс Музыку Ответьте на 1 вопрос и Яндекс Музыка ваша для вас и 3-х ваших близких. Кинопоиск и Яндекс Книги тоже в подписке. Попробуйте бесплатно❤️ Попробовать #реклама 18+ music.yandex.ru О рекламодателе Реклама на Яндексе

Задача: 133. Clone Graph Сложность: medium Дана ссылка на узел в связанном неориентированном графе. Верните глубокую копию (клон) графа. Каждый узел в графе содержит значение (целое число) и список (List[Node]) своих соседей. Пример:

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).

👨‍💻 Алгоритм: 1️⃣Используйте хеш-таблицу для хранения ссылок на копии всех уже посещенных и скопированных узлов. Ключом будет узел оригинального графа, а значением — соответствующий клонированный узел клонированного графа. Хеш-таблица посещенных узлов также используется для предотвращения циклов. 2️⃣Добавьте первый узел в очередь, клонируйте его и добавьте в хеш-таблицу посещенных. 3️⃣Выполните обход в ширину (BFS): извлеките узел из начала очереди, посетите всех соседей этого узла. Если какой-либо сосед уже был посещен, получите его клон из хеш-таблицы посещенных; если нет, создайте клон и добавьте его в хеш-таблицу. Добавьте клоны соседей в список соседей клонированного узла. 😎 Решение:

from collections import deque

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

class Solution:
    def cloneGraph(self, node: Optional["Node"]) -> Optional["Node"]:
        if not node:
            return node

        visited = {}
        queue = deque([node])
        visited[node] = Node(node.val, [])

        while queue:
            n = queue.popleft()
            for neighbor in n.neighbors:
                if neighbor not in visited:
                    visited[neighbor] = Node(neighbor.val, [])
                    queue.append(neighbor)
                visited[n].neighbors.append(visited[neighbor])
        return visited[node]

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

Как атакуют разработчиков? DevSecOps-трек на IT IS conf ИИнновации в безопасной разработке: как атакуют и спасают разработчика. На примерах из практики Денис Макрушин — директор по продуктам безопасной разработки в Yandex, расскажет, как распознавать такие угрозы и выстраивать устойчивость внутри разработки. • Ключевые угрозы и точки компрометации в процессе разработки • Подходы к снижению рисков на этапе SDLC • Без маркетинга — только применимые решения Выступление состоится 19 июня. Узнать больше #реклама 16+ itisconf.ru О рекламодателе

Задача: 1531. String Compression II Сложность: hard Дана строка s и целое число k. Необходимо удалить не более k символов из s так, чтобы длина сжатой версии строки s с использованием RLE была минимальной. Найдите минимальную длину сжатой версии строки s после удаления не более k символов. Пример:

Input: s = "aaabcccd", k = 2
Output: 4
Explanation: Compressing s without deleting anything will give us "a3bc3d" of length 6. Deleting any of the characters 'a' or 'c' would at most decrease the length of the compressed string to 5, for instance delete 2 'a' then we will have s = "abcccd" which compressed is abc3d. Therefore, the optimal way is to delete 'b' and 'd', then the compressed version of s will be "a3c3" of length 4.

👨‍💻 Алгоритм: 1⃣Обходим символы строки слева направо, решая для каждого символа, включать его в сжатую строку или нет. Это создает состояния (строка, оставшиеся для включения символы), которые можно представить в виде бинарного дерева, где левые потомки означают включение символов, а правые — их пропуск. Многочисленные повторяющиеся подзадачи указывают на необходимость использования динамического программирования. 2⃣Для определения состояния DP используем следующие параметры: количество пройденных символов (чтобы знать, какой символ обрабатывать следующим), последний добавленный символ в сжатую строку (чтобы определить изменение сжатия при добавлении нового символа), количество последнего символа (для правильного изменения длины сжатия при добавлении символа) и количество оставшихся символов, которые можно удалить. 3⃣Связываем состояния друг с другом: удаление нового символа увеличивает i на один и уменьшает k на один; включение нового символа оставляет длину сжатия неизменной (кроме случаев, когда частота последнего символа 1, 9 или 99) или увеличивает длину на один, если новый символ не равен последнему символу сжатия. 😎 Решение:

class Solution:
    def __init__(self):
        self.memo = {}
        self.add = {1, 9, 99}

    def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
        return self.dp(s, 0, chr(ord('a') + 26), 0, k)

    def dp(self, s: str, idx: int, last_char: str, last_char_count: int, k: int) -> int:
        if k < 0:
            return float('inf') / 2

        if idx == len(s):
            return 0

        key = idx * 101 * 27 * 101 + (ord(last_char) - ord('a')) * 101 * 101 + last_char_count * 101 + k

        if key in self.memo:
            return self.memo[key]

        delete_char = self.dp(s, idx + 1, last_char, last_char_count, k - 1)
        if s[idx] == last_char:
            keep_char = self.dp(s, idx + 1, last_char, last_char_count + 1, k) + (1 if last_char_count in self.add else 0)
        else:
            keep_char = self.dp(s, idx + 1, s[idx], 1, k) + 1

        res = min(keep_char, delete_char)
        self.memo[key] = res

        return res

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