Решаем кодом: найти самую длинную вложенную строку

Решаем кодом: найти самую длинную вложенную строку

Без повторных символов

Продолжаем разбирать задачи с сайта LeetCode. На этот раз — посложнее:

Есть строка s — нужно найти длину самой длинной подстроки, в которой каждый символ используется только один раз.

Например:

если s = "abcabcbb", то ответ будет 3, потому что строка без повторений — это "abc";

если s = "bbbbb", то ответ будет 1, потому что самая длинная подстрока тут будет из одного символа;

если s = "pwwkew", то ответ будет 3, потому что тут две самые одинаково длинные подстроки — "wke" и "kew", в которых по 3 символа.

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

Решение: использовать встроенные функции для работы со строками

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

Например, если у нас в подстроке хранится "abcdf" и мы снова встречаем b, то делаем так:

  1. Получаем номер символа b в подстроке → он равен 1 (если интересно, почему не 2, — почитайте, почему счёт в программировании начинается с нуля, а не с единицы).
  2. Формируем новую строку, начиная с 1 символа и до конца → "cdf".
  3. Добавляем к ней в конец наш текущий символ 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)

Решение: проверить всю вложенную строку

Зайдём с другой стороны — напишем функцию, которая будет проверять, есть в указанной подстроке повторяющиеся символы или нет. Логика будет такая:

  1. Передаём в функцию начальный и конечный индекс, который определяет границы подстроки.
  2. Заводим массив, в который будем складывать проверенные символы и проверять на дубли.
  3. По очереди проверяем все символы в указанном диапазоне и смотрим, есть ли очередной символ в нашем массиве.
  4. Если есть — выводим False, что означает, что в подстроке есть повторяющиеся символы.
  5. Если символа нет — добавляем его в наш массив.
  6. Если мы проверили все символы и ни одного не было в том массиве — возвращаем 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)

Текст:

Михаил Полянин

Редактор:

Максим Ильяхов

Художник:

Алексей Сухов

Корректор:

Ирина Михеева

Вёрстка:

Кирилл Климентьев

Соцсети:

Виталий Вебер

Получите ИТ-профессию
В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства.
Начать карьеру в ИТ
Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию
medium