Продолжаем разбирать задачи с сайта LeetCode. На этот раз — посложнее:
Есть строка s — нужно найти длину самой длинной подстроки, в которой каждый символ используется только один раз.
Например:
если s = “abcabcbb”, то ответ будет 3, потому что строка без повторений — это “abc”;
если s = “bbbbb”, то ответ будет 1, потому что самая длинная подстрока тут будет из одного символа;
если s = “pwwkew”, то ответ будет 3, потому что тут две самые одинаково длинные подстроки — “wke” и “kew”, в которых по 3 символа.
Такие алгоритмы иногда используются для выявления закономерностей и поиска общих элементов, поэтому их тоже могут спросить на собеседованиях.
Разбор: задача про массив и сумму чисел
Задача с собеседования: как найти палиндром
Задача с собеседования про перебор букв в словах
Как компьютер находит неправильные скобки и кавычки
Списки (массивы) в Python и работа с ними
Как быстро найти нужное место в списке
Что делать, когда Python сам меняет значения списка
Разбираемся с массивами в Python: кортежи
Разбираемся с массивами в Python: словариРешение: использовать встроенные функции для работы со строками
Самое простое решение — собирать отдельную подстроку из символов и смотреть каждый раз, есть очередной символ в этой подстроке или нет. Если нет — добавляем его в конец и смотрим дальше. А если очередной символ там уже есть, то в подстроке оставляем только то, что идёт после этого символа, и добавляем туда текущий.
Например, если у нас в подстроке хранится “abcdf” и мы снова встречаем b, то делаем так:
- Получаем номер символа b в подстроке → он равен 1 (если интересно, почему не 2, — почитайте, почему счёт в программировании начинается с нуля, а не с единицы).
- Формируем новую строку, начиная с 1 символа и до конца → “cdf”.
- Добавляем к ней в конец наш текущий символ b → “cdfb”.
Так шаг за шагом мы проверим все вложенные строки и найдём самую длинную без повторов. Звучит сложно, но в коде всё выглядит гораздо проще. Почитайте комментарии, чтобы разобраться в каждом шаге:
# исходная строка
s = 'abcabcdcc'
# здесь будет наш ответ
res = 0
# на старте у нас пустая подстрока
sub = ''
# перебираем все символы в исходной строке
for char in s:
# если символа нет в подстроке
if char not in sub:
# добавляем его туда
sub += char
# смотрим, максимальный ли это результат, и если да — запоминаем его
res = max(res, len(sub))
# если символ в подстроке есть
else:
# получаем индекс текущего символа в подстроке
cut = sub.index(char)
# сокращаем нашу подстроку: оставляем только то, что идёт после символа-дубликата, и добавляем к строке текущий символ
sub = sub[cut+1:] + char
# выводим результат на экран
print(res)Решение: проверить всю вложенную строку
Зайдём с другой стороны — напишем функцию, которая будет проверять, есть в указанной подстроке повторяющиеся символы или нет. Логика будет такая:
- Передаём в функцию начальный и конечный индекс, который определяет границы подстроки.
- Заводим массив, в который будем складывать проверенные символы и проверять на дубли.
- По очереди проверяем все символы в указанном диапазоне и смотрим, есть ли очередной символ в нашем массиве.
- Если есть — выводим False, что означает, что в подстроке есть повторяющиеся символы.
- Если символа нет — добавляем его в наш массив.
- Если мы проверили все символы и ни одного не было в том массиве — возвращаем True, то есть повторов нет.
Теперь запишем это на Python:
# исходная строка
s = 'abcabcdcc'
# функция, которая проверит, есть ли в подстроке повторяющиеся символы
# на вход отправляем начальную и конечную позицию в строке для проверки
def check(start, end):
# создаём пустое множество
chars = set()
# делаем цикл от начального до конечного символа
for i in range(start, end + 1):
# получаем очередной символ из строки
c = s[i]
# если символа уже есть в множестве
if c in chars:
# возвращаем False — в строке есть повторяющиеся символы
return False
# добавляем символ в множество
chars.add(c)
# если дошли досюда — возвращаем True
return TrueТеперь перейдём к основной части. Раз мы научились проверять, есть повторы в подстроке или нет, то нам остаётся только найти и проверить все вложенные строки. Сделаем это обычным перебором с вложенным циклом: будем проверять все подстроки, сначала начиная с первого символа, потом со второго и так далее. При этом мы будем каждый раз считать и запоминать максимальную длину подстроки без повторов, которая у нас получилась:
# --- основной алгоритм ---
# получаем длину строки
n = len(s)
# здесь будет наш ответ
res = 0
# перебираем символы от первого до последнего
for i in range(n):
# перебираем символы от текущего до последнего
for j in range(i, n):
# если в получившейся подстроке нет повторяющихся символов
if check(i, j):
# смотрим, максимальный ли это результат, и если да — запоминаем его
res = max(res, j - i + 1)
# выводим результат на экран
print(res)Объединим обе части и получим готовый код:
# исходная строка
s = 'abcabcdcc'
# функция, которая проверит, есть ли в подстроке повторяющиеся символы
# на вход отправляем начальную и конечную позицию в строке для проверки
def check(start, end):
# создаём пустое множество
chars = set()
# делаем цикл от начального до конечного символа
for i in range(start, end + 1):
# получаем очередной символ из строки
c = s[i]
# если символа уже есть в множестве
if c in chars:
# возвращаем False — в строке есть повторяющиеся символы
return False
# добавляем символ в множество
chars.add(c)
# если дошли досюда — возвращаем True
return True
# --- основной алгоритм ---
# получаем длину строки
n = len(s)
# здесь будет наш ответ
res = 0
# перебираем символы от первого до последнего
for i in range(n):
# перебираем символы от текущего до последнего
for j in range(i, n):
# если в получившейся подстроке нет повторяющихся символов
if check(i, j):
# смотрим, максимальный ли это результат, и если да — запоминаем его
res = max(res, j - i + 1)
# выводим результат на экран
print(res)
