Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

 

Example 1:

Input: s = "abcabcbb"

Output: 3

Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"

Output: 1

Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"

Output: 3

Explanation: The answer is "wke", with the length of 3.

Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Решение:

class Solution:

def lengthOfLongestSubstring(self, s):

if len(s)==0:

return 0

accumSet=set()

maxLen=0

currLen=0

startIdx=-1

endIdx=-1

while True:

isDuplicate=False

while endIdx<len(s)-1:

endIdx+=1

endChar=s[endIdx]

if endChar not in accumSet:

accumSet.add(endChar)

# Здесь запоминается максимальная длинна участка

currLen=endIdx-startIdx

if currLen>maxLen:

maxLen=currLen

# print("maxLen: "+str(maxLen))

else:

isDuplicate=True

break

if isDuplicate:

while startIdx<len(s)-1:

startIdx+=1

startChar=s[startIdx]

if startChar!=s[endIdx]:

accumSet.discard(startChar)

continue

else:

break

if endIdx>=len(s)-1:

break

return maxLen

Пояснение:

Идея в том, чтобы иметь два "указателя".

startIdx - это указатель начала исследуемой подстроки (самый левый символ подстроки)

endIdx - это указатель конца исследуемой подстроки (самый правый символ подстроки)

А так же нужен объект-множество, который хранит символы, которые есть в исследуемой подстроке.

Движение указателей происходит в два этапа, эти этапы заключены в цикл пока не закончится входная строка. Указатели ползут вправо. Начальное положение указателей - самый первый символ строки. Указатель startIdx не может "обогнать" endIdx.

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

На втором этапе вправо ползет указатель startIdx. Каждый символ проверяется на соответствие символу, находящемося по индексу endIdx, ведь он является повторным (его можно назвать вторым повторным символом). Задача перемещения startIdx в том, чтобы найти первый повторный символ и установиться справа от него. При поиске этого повторного символа каждый просмотренный символ удаляется из set, ведь в подстроке между startIdx и endIdx он будет отсутствовать.

Далее цикл повторяется.

Когда endIdx доберется до последнего символа, цикл заканчивается.

Возможные способы улучшения (не реализовано):

- Нет смысла проверять последние символы строки, если endIdx добрался до последнего символа, а startIdx перевалил за endIdx - maxLen, так как после этого момент все найденные подстроки будут короче, чем уже найденная максимальная подстрока.