Чтобы найти самую длинную подстроку заданной строки, содержащую только отдельные символы, вы можете использовать метод скользящего окна. Это включает в себя поддержание окна символов в строке и многократное перемещение окна по строке, отслеживая длину самой длинной подстроки с различными символами, которые вы видели до сих пор. Вот пример того, как вы можете реализовать этот подход в Python:
def longest_distinct_substring(s):
char_set = set()
max_len = 0
start = 0
for i in range(len(s)):
while s[i] in char_set:
char_set.remove(s[start])
start += 1
char_set.add(s[i])
max_len = max(max_len, i - start + 1)
return max_len
Эта функция принимает строку в качестве входных данных и возвращает длину самой длинной подстроки, содержащей различные символы. Переменная char_set используется для отслеживания символов в текущем окне, а переменная start отслеживает начальный индекс текущего окна. Цикл for перебирает каждый символ во входной строке, а цикл while перемещает начальный индекс окна вперед до тех пор, пока он не перестанет содержать повторяющийся символ. Каждый раз, когда в окно добавляется новый символ, длина текущего окна сравнивается с максимальной длиной, видимой до сих пор, и максимальная длина обновляется, если текущее окно длиннее.
Что такое временная сложность и пространственная сложность?
Временная сложность алгоритма составляет O(n), где n — длина входной строки. Это связано с тем, что алгоритм повторяет каждый символ во входной строке один раз, а операции в циклах for и while занимают постоянное время.
Пространственная сложность алгоритма равна O(k), где k – количество различных символов во входной строке. Это связано с тем, что алгоритм использует набор для отслеживания символов в текущем окне, а количество элементов, которые могут быть сохранены в наборе, ограничено количеством различных символов во входной строке.
Подпишитесь на меня в LinkedIn: -
https://www.linkedin.com/in/tejas-khartude-7601b640/
Следите за моим вкладом с открытым исходным кодом здесь: -
Удачного кодирования….. :)
