LeetCode День 2 Longest Substring Without Repeating Characters [Medium]⁠⁠

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

https://leetcode.com/problems/longest-substring-without-repe...

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

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

Сначала определим словарь, куда будем складывать длинны строк и значения этих самых строк. Для определения уникальности символов в строке просто считаем количество вхождений для каждого символа в отдельной функции. Ну а в цикле будем пробегать по всем подстрокам этой строки. Получилось практически с первого раза и я уже решил, что задаче надо сменить уровень на easy:

Действительно это будет работать для относительно коротких строк, но я не обратил внимание на мелкий шрифт в конце:

Т.е. на вход может подаваться текст на 50000 знаков. На одном из кейсов я закономерно получил ошибку, и даже перенеся на локальную машину подсчёты затянулись на 10+ минут, дальше я просто прервал исполнение.

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

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

Стало очевидно, что надо как то уменьшить количество пустых итераций, ну не может же быть, что очень длинный текст набран только уникальными символами. Ну и логично, что размер искомой подстроки не может быть больше количества уникальных символов в этой строке. Значит сначала надо подсчитать количество уникальных символов в строке и этим числом ограничить начальный размер искомой подстроки, а не полной длиной строки.

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

Ну и бонусом решение от chatGpt, которое оказалось намного лучше моего:

В целом собой доволен, но решение от chatGpt опять вгоняет меня в уныние. Мало того, что бот сделал быстрее чем я, он сделал сильно лучше, чем я.