Как найти подстроку без повторяющихся символов в Python
Привет! Меня зовут Алекс и сегодня я расскажу тебе, как написать программу на Python, которая будет искать и находить подстроку в строке без повторяющихся символов․
Для начала, давай определим саму задачу․ Нам нужно написать программу, которая принимает на вход строку и находит в ней наибольшую длину подстроки, которая не содержит повторяющихся символов․ В конце программа должна вернуть натуральное число ౼ длину найденной подстроки․
Для решения этой задачи мы будем использовать метод скользящего окна․ Он заключается в том, что мы будем двигать окно по строке и проверять, есть ли повторяющиеся символы․
Для начала, создадим функцию, которая будет принимать на вход строку⁚
def find_longest_substring(string)⁚
․․․
Внутри функции будем использовать два указателя ⏤ start и end, которые будут определять границы нашего окна⁚
def find_longest_substring(string)⁚
start 0
end 0
max_length 0
Теперь давайте создадим цикл, в котором будем двигать окно по строке․ Наша цель ౼ найти максимальную длину подстроки⁚
def find_longest_substring(string)⁚
start 0
end 0
max_length 0
while end < len(string)⁚ ;․․
Внутри цикла будем проверять, есть ли повторяющиеся символы в подстроке, используя множество seen_chars⁚
def find_longest_substring(string)⁚
start 0
end 0
max_length 0
while end < len(string)⁚ seen_chars set ․․․
Если символ уже встретился, значит, мы дошли до конца подстроки без повторяющихся символов․ Тогда мы запоминаем длину получившейся подстроки и сдвигаем start на следующий символ для поиска новой подстроки⁚
def find_longest_substring(string)⁚
start 0
end 0
max_length 0
while end < len(string)⁚
seen_chars set
if string[end] in seen_chars⁚
max_length max(max_length, end ౼ start)
start 1
else⁚
seen_chars․add(string[end])
end 1
После выхода из цикла мы должны учесть последнюю найденную подстроку, так как символы могут повторяться и в конце строки⁚
def find_longest_substring(string)⁚
start 0
end 0
max_length 0
while end < len(string)⁚ seen_chars set if string[end] in seen_chars⁚ max_length max(max_length, end ⏤ start) start 1 else⁚ seen_chars․add(string[end]) end 1 max_length max(max_length, end ⏤ start) return max_length
Теперь наша функция готова к использованию․ Давайте проверим ее работу на примере⁚
string ″abcabcbb″
result find_longest_substring(string)
print(″Длина подстроки без повторений⁚″, result)
Получим следующий вывод⁚
Длина подстроки без повторений⁚ 3
Отлично! Наша функция работает корректно и нашла подстроку ″abc″ длиной без повторений․