Решенные задачи

1 - Two sum
2 - Add two numbers
3 - Longest Substring Without Repeating Characters
4 - Median of Two Sorted Arrays
5 - Longest Palindromic Substring
10 - Regular Expression Matching
11 - Container With Most Water
15 - 3Sum
33 - Search in Rotated Sorted Array
53 - Maximum Subarray
121 - Best Time to Buy and Sell Stock
152 - Maximum Product Subarray
153 - Find Minimum in Rotated Sorted Array
217 - Contains Duplicate
238 - Product of Array Except Self

По сложности

#easy
#medium
#hard

По темам и методам решения

#strings
#arrays
#linkedlists
#dp
#divideandconquer
#twopointers
#hashtable
#prefixsum

#ретро

[Условие] Leetcode #3. Longest Substring Without Repeating Characters

Ссылка на задачу на Leetcode
Решение

На вход дается строка s. Нужно найти самую длинную подстроку без повторений.

Пример #1:
s = 'abcabcbb'
output: 3 // 'abc'

Пример #2:
s = 'bbbbb'
output: 1 // 'b'

Пример #3:
s = 'pwwkew'
output: 3 // 'wke'

Ограничения:
- длина строки до 5 * 10^4
- содержать может английские буквы, цифры, символы и пробелы

#medium #strings

@leetcode_furrycat

[Решение] Leetcode #3. Longest Substring Without Repeating Characters

Условие задачи

Идея в том, чтобы использовать хеш-таблицу для отслеживания уже встреченных символов. Если текущий символ уже встречался, значит, строка без повторений закончилась: можно вычислить ее длину и начать новую строку с символа, который следует за этим повторением.

Пример для s = abcbac:

- считаем подстроку с нулевого символа (currentIndex = 0)
- перебираем символы по одному и заносим их в хеш вместе с индексами: { a: 0, b: 1, c: 2 }
- текущий индекс 3 - i = 3, символ b, видим, что он уже встречался на 1-й позиции. Значит, строка без повторений кончилась. Сохраняем ее длину (с нулевого символа до 3 невключительно: max = 3)
- обновляем индекс символа b в хеше: { a: 0, b: 3, c: 2 }
- начинаем новый отсчет со следующего за повторенным символа (currentIndex = 2)
- i = 4, символ a - сохраненный индекс 0, но это меньше, чем начало нашей текущей подстроки, так что можно считать, что символа a у нас еще не было.
- i = 5, символ c - сохраненный индекс 2 - это попадает в нашу строку, поэтому заканчиваем ее. Длина полученной подстроки равна 3 (со 2-го по 5 символ невключительно). Она не больше текущего max, так что можно не перезаписывать.

Итого, ответ 3.

Видео с разбором
Тут немного другая структура, но в целом похоже на мое решение. Кажется даже, что мое немного эффективнее, так как в нем нет доп. цикла для удаления ненужных символов.

#medium #strings

@leetcode_furrycat

[Условие] Leetcode #5. Longest Palindromic Substring

Ссылка на задачу на Leetcode
Решение

На вход получаем строку s, необходимо найти самую длинную подстроку, которая является палиндромом (читается в обе стороны одинаково).

Ограничения:

- длина строки s = [1, 1000]
- строка s состоит только из английских букв и цифр

#medium #strings

@leetcode_furrycat

[Решение] Leetcode #5. Longest Palindromic Substring

Условие задачи

Проходимся в цикле по всем символам строки. Для каждого символа (`currentIndex`) определяем палиндромную строку с этим символом в центре - то есть начинаем с этого символа и пытаемся наращивать подстроку в обе стороны до тех пор, пока она остается палиндромом.

Для набираемой подстроки нужно хранить индекс начала (`left`) и конца (`right`). Изначально left = currentIndex, right = currentIndex.

Начинать следует с последовательности одинаковых символов любой длины - это ядро палиндрома. То проверяем правые от currentIndex символы, если они одинаковые, раздвигаем, отодвигаем right.

Когда одинаковые символы закончились, пробуем расширять подстроку по одному символу в обе стороны сразу. Если слева и справа от нее находятся одинаковые символы, значит, она продолжает оставаться палиндромом, можно сдвинуть left и right.

Потом просто находим самый длинный палиндром из полученных.

#medium #strings

@leetcode_furrycat