🟡 Medium
567. Permutation in String

Пример:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 содержит одну перестановку s1 ("ba").

Подсказка: какое общее свойство у строк, одна из которых является перестановкой другой?

26/200
#medium
#leetcode567

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

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

📝 Идея
▫️Поскольку все символы в строке заглавные буквы, их количество в текущей подстроке считаем с помощью массива размером 26
▫️Условием для того, что подстрока подходит под возможный ответ:
- разница длины подстроки и самого встречающегося символа должна быть меньше или равна k, иначе удаляем символ с левого края

#solution424

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

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

📝 Идея
▫️Строка, которая является перестановкой другой строки имеет такое же количество символов, поэтому, перебирая вторую строку, сравниваем - если массивы строк count1 и count2 одинаковые, значит мы нашли нужную подстроку
▫️При этом следим, чтобы размер "окна" совпадал с размером строки s1, поэтому удаляем левый символ, если размер стал больше

#solution567

🔴 Hard
239. Sliding Window Maximum

Подсказка: для решения используйте deque - двустороннюю очередь

27/200
#hard
#leetcode239

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

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

📝 Идея
▫️ В dq храним индексы массива и на каждом шаге делаем следующее:
1. Если первый элемент в очереди выходит за пределы "окна" - удаляем его
2. Удаляем верхний элемент очереди, пока он меньше текущего
▫️Таким образом первый элемент в dq — всегда индекс самого большого элемента в текущем окне

#solution239

Базовая задача, решение, как всегда, оказалось простым, но необходимо понять его принцип.
Он обязательно пригодится для решения задач на различных контестах, а кому-то может попасться похожая задача на собеседовании

🔴 Hard
76. Minimum Window Substring

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

28/200
#hard
#leetcode76

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

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

📝 Идея
▫️ С помощью правого указателя находим окно, в котором содержатся все символы из строки t, далее левым указателем сужаем окно для минимального ответа
▫️Эффективно искать минимальное окно нам помогает массив, в котором мы храним частоту символов

#solution76

✅ Как и любая hard-задача, данная не стала исключением и породила множество неэффективных и сложных решений.
Однако это решение крайне быстрое и простое, что показывает и статистика на LeetCode

🟢 Easy
206. Reverse Linked List

Класс ListNode:

public class ListNode { 
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { 
        this.val = val; 
    }
    ListNode(int val, ListNode next) {
        this.val = val; 
        this.next = next; 
    }
}

Подсказка: сохраняйте предыдущий и следующий узел

29/200
#easy
#leetcode206

🟢 Easy
21. Merge Two Sorted Lists

📃 Вам даны заголовки двух отсортированных связанных списков list1и list2.
Объедините два списка в один отсортированный список.

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

30/200
#easy
#leetcode21

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

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

📝 Идея
▫️Создаем новый корень двух списков и текущий узел
▫️Проходимся по двум спискам, сохраняя наименьший из узлов
▫️В конце останется непустым один из списков, поэтому сохраняем на него ссылку

#solution21

🟡 Medium
19. Remove Nth Node From End of List

📃 Дан связанный список, удалить n-ый с конца узел

Подсказка: используйте два указателя и сдвиньте один из них на n вперед

31/200
#medium
#leetcode19

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

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

📝 Идея
▫️Указатель right сдвигаем на n вперед, а left инициализируем левее head
▫️Теперь при простой итерации до момента, когда right окажется за пределами списка, left будет находиться как раз на позиции (n+1) c конца
▫️Остается только изменить ссылку на следующий узел ссылкой через один, тем самым удалив n-ый узел с конца

#solution19

🟡 Medium
33. Search in Rotated Sorted Array

📃 Массив nums отсортирован по возрастанию и имеет различные значения, но при этом возможен поворот (как здесь)
Вернуть индекс target, если он находится в nums и -1, если нет

Необходимо написать алгоритм, который работает за O(log(n))

Подсказка: используйте бинарный поиск, проверяя значения элементов nums[l] и nums[mid] для правильного перемещения указателей

32/200
#medium
#leetcode33

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

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

📝 Идея
▫️Используем бинарный поиск, при этом проверяя значение элемента под индексом mid:
- если nums[l] <= nums[mid], значит мы находимся на отсортированной части массива без поворотов
- если нет, значит мы находимся на отрезке, где значения в левой части больше центральных
▫️Исходя из позиции, кроме обычных проверок бинарного поиска, также проверяем отношение target к указателям, чтобы передвигать mid к элементам ближе по значению к target

#solution33

🔴 Hard
4. Median of Two Sorted Arrays

📃 Даны два отсортированных массива nums1 и nums2 размером m и n, вернуть медиану двух отсортированных массивов

Необходимо написать алгоритм, который работает за O(log(m+n))

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

33/200
#hard
#leetcode4

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

Time: O(log(min(n, m)))
Space: O(1)

📝 Идея
▫️Используя бинарный поиск по меньшему из массивов, находим такой элемент, который при соединении двух массивов будет являться серединой
Для этого должны выполняться условия:
- максимальный элемент из левой части отрезка nums1 должен быть меньше минимального элемента из правой части отрезка nums2 и также наоборот, тогда два массива разделены правильно на две части
▫️Присвоение максимальных и минимальных значений используем для того, чтобы логика алгоритма не рушилась, если mid оказался за пределами массива

#solution4

🟡 Medium
143. Reorder List

Подсказка: найдите середину списка и переверните его вторую часть

34/200
#medium
#leetcode143