✅ Решение задачи 798

Time: O(n)
Space: O(n)

💡 Идея
🟦создаем массив diff[] размером n, который будет хранить изменения количества баллов при каждом сдвиге

🟦далее проходим по массиву и для каждого элемента рассчитываем, при каком сдвиге данный элемент перестанет давать баллы: k = (i - nums[i] + 1 + n) % n, а затем уменьшаем diff[k] на 1, чтобы учесть, что при таком сдвиге баллы уменьшаются

🟦теперь будем накапливать изменения для каждого сдвига от 1 до n, проходя по массиву diff и суммируя их, при этом учитываем, что каждый новый элемент дает +1 балл, потому что в конец массива попадает новый элемент, который точно дает баллы, так как элементы массива по условию от 0 до n

🟦для каждого сдвига проверяем, сколько баллов получилось и, если это количество больше, чем для предыдущих сдвигов, обновляем результат

❔Почему k вычисляется именно так?
▫i: исходная позиция элемента
▫- nums[i]: смещаемся назад настолько, насколько велик сам элемент
▫+ 1: смещаемся еще на одну позицию, чтобы теперь элемент не давал баллы
▫+ n: гарантируем, что выражение не будет отрицательным
▫% n: берем по модулю, чтобы остаться в пределах массива

❔Почему изменения для каждого сдвига суммируются?
➖вычисляя k, мы определяем самую правую позицию, в которой данный элемент не приносит баллы, соответственно при большем сдвиге он сдвигается левее, где также не будет приносить баллы, поэтому мы последовательно суммируем изменения для каждого сдвига. При этом мы учитываем, что массив цикличный, на каждом шаге добавляя в cur +1 для элемента, который перешел в конец массива

👩‍💻 Java Algo | #solution798

➡️ Стартуем тему скользящего окна

💡 Идея

Представим, что ты следишь за своими расходами и всегда хочешь знать, сколько денег ты потратил за последние 7 дней.

Вместо того, чтобы каждый день пересчитывать все с нуля, ты хранишь текущую сумму за последние 7 дней, каждый день добавляешь новую трату и вычитаешь трату, которая была 8 дней назад.

Таким образом, у тебя всегда актуальная сумма за последние 7 дней без необходимости считать ее всю постоянно.

#slidingwindow

🟢Easy
1652. Defuse the Bomb

Company: 🏢📱📱

📝Дан массив code и целое число k.

Необходимо заменить каждый элемент по следующим правилам:
▫если k > 0, замените элемент суммой следующих k чисел
▫если k < 0, замените элемент суммой предыдущих k чисел
▫если k == 0, замените элемент на 0

Массив code является круговым, поэтому следующим элементом code[n-1] является code[0], а предыдущим элементом code[0] является code[n-1].

Верните полученный массив

💡: при выходе указателя за пределы, берите для него остаток от деления на длину массива

#leetcode1652 | #easy #slidingwindow

✅ Решение задачи 1652

Time: O(n)
Space: O(n)

💡 Идея
🟦инициализируем массив для записи результата размером исходного (n) и сразу возвращаем его, если k == 0

🟦инициализируем два указателя: на начало окна start = 1 и конец end = k, но если k < 0, меняем позиции на start = n - |k| и end = n - 1, то есть устанавливая окно перед нулевым элементом

🟦далее считаем сумму в полученном окне, чтобы затем эффективно считать остальные

🟦проходим по исходному массиву, записываем в результат текущую сумму и формируем новую для следующего элемента:

▫из текущей суммы вычитаем элемент на позиции старта окна (start % n) и добавляем элемент следующий после конца ((end + 1) % n), то есть считаем сумму для следующего окна, меняя только границы, при этом все содержимое между остается неизменным, поэтому мы получаем ее правильно

▫затем увеличиваем указатели start и end, фактически передвигая окно на следующую позицию

🟦в конце возвращаем полученный массив c результатом

👩‍💻 Java Algo | #solution1652

🟢Easy
2379. Minimum Recolors to Get K Consecutive Black Blocks

Company: 🔍📱💻

📝Дана строка, которая содержит символы 'W' и 'B', представляющие белый и черный цвета соответственно. Также дано целое число k— желаемое количество последовательных черных блоков.

За одну операцию вы можете перекрасить белый блок в черный.

Верните минимальное количество операций, необходимое для того, чтобы было хотя бы одно вхождение последовательных k черных блоков

💡: найдите минимальное количество белых блоков в окне

#leetcode2379 | #easy #slidingwindow

✅ Решение задачи 2379

Time: O(n)
Space: O(1)

💡 Идея
🟦чтобы найти минимальное количество операций, будем искать минимальное количество белых блоков в окне длиной k, вычитая из него количество черных блоков

🟦проходим по строке и увеличиваем счетчик, если текущий символ 'B'

🟦как только, индекс стал больше или равен k, значит мы уже вышли за пределы окна и нужно удалить элемент слева: уменьшаем счетчик, если символ i - k = 'B'

🟦на каждом шаге проверяем минимальное количество белых блоков, как длину окна (k) минус количество черных блоков

👩‍💻 Java Algo | #solution2379

🟡Medium
2516. Take K of Each Character From Left and Right

Company: 🔍📱🏢

📝Дана строка s, состоящая из символов 'a', 'b' и 'c', и целое число k. Каждую минуту вы можете взять либо самый левый символ s, либо самый правый символ s.

Верните минимальное количество минут, необходимое для того, чтобы взять не меньше k каждого символа или -1, если это невозможно

💡: найдите максимальное окно, которое можно удалить, чтобы в оставшейся части строки выполнялось условие

#leetcode2516 | #medium #slidingwindow

✅ Решение задачи 2516

Time: O(n)
Space: O(1)

💡 Идея

🟦для решения будем искать самое большое окно из символов такое, что в оставшейся части строки (слева и справа) будут символы, которые удовлетворяют условию по количеству, а затем вычтем его из длины строки

🟦инициализируем массив count размером 3 для подсчета частоты каждого символа и заполняем его, проходя по исходной строке

🟦сразу возвращаем -1, если любой из символов встречается меньше k раз

🟦далее инициализируем массив window для подсчета символов в текущем окне и проходим по исходной строке правым указателем:

➖добавляем частоту текущего символа в массив window
➖если за пределами окна находится меньше k текущего символа, передвигаем левый указатель, пока это условие верно, уменьшая частоту символов под ним
➖считаем максимальную длину окна, используя левый и правый указатели

🟦в конце возвращаем результат: длина строки минус максимальная длина окна

👩‍💻 Java Algo | #solution2516

🟡Medium
2461. Maximum Sum of Distinct Subarrays With Length K

Company: 📱📱🏢

📝Дан массив целых чисел nums и целое число k.

Найдите максимальную сумму подмассива длиной k, в котором все элементы различны

💡: сохраняйте в HashMap позиции элементов для исключения дубликатов в окне

#leetcode2461 | #medium #slidingwindow

✅ Решение задачи 2461

Time: O(n)
Space: O(n)

💡 Идея
🟦инициализируем HashMap, в котором будем хранить позиции элементов, чтобы затем использовать их для исключения дубликатов из окна

🟦проходим по массиву правым указателем и на каждом шаге:
➖считаем текущую сумму

➖берем из HashMap последнюю позицию текущего элемента lastPos, если он встречался или -1, если нет

➖передвигаем левый указатель, вычитая из суммы элементы под ним, пока выполняется одно из условий:
▫он меньше или равен lastPos (то есть исключаем дубликат из окна)
▫размер окна превышает k

➖кладем в HashMap текущий элемент и его позицию и считаем максимальный результат, если размер текущего окна равен k

👩‍💻 Java Algo | #solution2461

🟡Medium
2134. Minimum Swaps to Group All 1's Together II

Company: 📱🔍🅰️

📝Для заданного двоичного циклического массива nums верните минимальное количество перестановок, необходимых для группировки всех единиц, присутствующих в массиве, в любом месте

💡: найдите минимальное кол-во нулей в окне размером общего кол-ва единиц

#leetcode2134 | #medium #slidingwindow

✅ Решение задачи 2134

Time: O(n)
Space: O(1)

💡 Идея

🟦поскольку сгруппировать единицы можно в любом месте, нужно найти такое окно размером общего количества единиц, в котором будет меньше всего позиций для перестановок, то есть нулей

🟦посчитаем общее кол-во единиц в переменной total и проходим до данного значения правым указателем, подсчитывая текущее кол-во единиц (формируем начальное окно)

🟦инициализируем левый указатель на нулевой элемент, проходим им по массиву и на каждом шаге:
➖обнуляем правый указатель, если он вышел за пределы массива, тем самым учитывая цикличность

➖вычитаем из текущего кол-ва единиц элемент под левым указателем и добавляем элемент под правым

➖считаем минимальное кол-во нулей в окне, вычитая из общего кол-ва единиц текущее, и передвигаем указатели

👩‍💻 Java Algo | #solution2134

🟡Medium
1234. Replace the Substring for Balanced String

Company: 📱

📝Дана строка s, содержащая только четыре вида символов: 'Q', 'W', 'E', и 'R'.
Строка называется сбалансированной, если каждый из ее символов появляется n / 4 раз, где n — длина строки, всегда кратная 4.

Верните минимальную длину подстроки, которую можно заменить любой другой строкой той же длины, чтобы сделать всю строку s сбалансированной

💡: найдите минимальное окно для замены, проверяя оставшуюся часть строки на сбалансированность, используя массив частот

#leetcode1234 | #medium #slidingwindow

✅ Решение задачи 1234

Time: O(n)
Space: O(1)

💡 Идея
🟦инициализируем массив freq для подсчета частоты символов и проходим по всей строке, заполняя его

🟦далее проходим по строке и ищем минимальное окно, после замены (удаления) которого в оставшейся строке все символы не будут превышать n / 4 по частоте:
➖уменьшаем текущую частоту символа (добавляем его в окно)
➖пытаемся уменьшить окно, передвигая его левую границу, пока верно условие, что частота всех символов не превышает n / 4, одновременно считая минимальное окно и добавляя частоты символов под левым указателем (убираем из окна)

📎функция isBalanced:

private boolean isBalanced(int[] freq, int target) {
for (int num : freq) {
if (num > target) {
return false;
}
}
return true;
}

👩‍💻 Java Algo | #solution1234

🟡Medium
904. Fruit Into Baskets

Company: 🏢📱🅰️

📝Дан массив fruits, где fruits[i] — тип фрукта. У вас есть 2 корзины, в каждой может находится только 1 тип фруктов (неограниченного количества).

Начиная с любой позиции, двигайтесь вправо, собирая фрукты, пока они помещаются в ваши корзины. Верните максимальное количество фруктов, которое можно собрать

💡: поддерживайте окно с двумя уникальными элементами

#leetcode904 | #medium #slidingwindow

✅ Решение задачи 904

Time: O(n)
Space: O(k)

💡 Идея
🟦для решения будем искать максимальное окно с двумя уникальными элементами

🟦проходим по массиву правым указателем и на каждом шаге:
➖кладем в HashMap текущий элемент и увеличиваем его частоту

➖если "корзин" в HashMap стало больше 2:
пока это условие верно, передвигаем левый указатель, уменьшая частоту элементов под ним, и удаляем элемент из HashMap, если его частота стала равна 0

➖считаем максимальное окно, используя левый и правый указатели

👩‍💻 Java Algo | #solution904

🔴Hard
2009. Minimum Number of Operations to Make Array Continuous

Company: 🚖🔍🅰️

📝Вам дан массив целых чисел nums, за одну операцию вы можете заменить любой элемент в нем любым целым числом.

Массив считается непрерывным, если выполняются оба следующих условия:
▫все элементы уникальны
▫разница между максимальным и минимальным элементами равна длине массива минус 1

Верните минимальное количество операций, необходимое для создания непрерывного массива

💡: найдите максимальное окно, в котором выполняется условие, предварительно отсортировав массив из уникальных элементов

#leetcode2009 | #hard #slidingwindow

✅ Решение задачи 2009

Time: O(nlogn)
Space: O(n)

💡 Идея

🟦для решения найдем максимальное окно (подмассив), в котором все элементы уникальны и максимальный элемент не превышает минимальный плюс длина исходного массива.
При этом нам не нужно думать, как заменить оставшиеся элементы, так как необходимо вывести только количество операций. Также нам не важен порядок элементов, а только минимальный и максимальный, поэтому их можно отсортировать для удобного поиска

🟦с помощью HashSet возьмем из исходного массива только уникальные элементы, создадим для них новый массив и отсортируем его

🟦далее проходим по новому массиву левым указателем и ищем максимальный подмассив, который является непрерывным:
➖передвигаем правый указатель, пока элемент под ним меньше левого элемента плюс длина исходного массива
➖считаем максимальное окно, используя левый и правый указатели

👩‍💻 Java Algo | #solution2009

🔴Hard
30. Substring with Concatenation of All Words

Company: 🔍🏢🅰️

📝Вам дана строка s и массив строк words, которые имеют одинаковую длину.

Сцепленная строка — это строка, которая содержит в точности все строки любой перестановки words.

Верните список начальных индексов всех сцепленных подстрок в s

💡: поддерживайте окно длиной всех слов из words, для их подсчета используя HashMap

#leetcode30 | #hard #slidingwindow