День 5: Задача «Самая длинная подстрока без повторяющихся символов»
Проблема:
Для заданной строки найдите длину самой длинной подстроки без повторяющихся символов.
Пример:
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Мое решение:
class Solution(object):
def lengthOfLongestSubstring(self, s):
if len(s) <= 1:
return len(s);
arr = [1 for i in range(len(s))]
max_val = 0
for i in range(1,len(s)):
for j in range(i-1, i-arr[i-1]-1, -1):
if(s[j] != s[i]):
arr[i] += 1
else:
break;
max_val = max(max_val, arr[i])
return max_val
Пояснение:
Это классическая задача динамического программирования.
Теперь давайте возьмем этот пример:
Давайте сопоставим то, что мы знаем на данный момент:
- Каждая буква в строке сама по себе является «подстрокой без повторяющегося символа».
- Чтобы проверить, нет ли в подстроке повторяющихся символов, нам нужно проверить, не совпадает ли каждая буква в подстроке с какой-либо другой буквой в подстроке.
Идея: в каждой позиции мы можем найти максимальную подстроку без повторяющихся символов, которая заканчивается в этой позиции. Если мы это знаем, то подстрока с максимальной длиной среди них и будет подстрокой, которую мы ищем.
Чтобы запомнить вывод каждой итерации, мы будем поддерживать один массив для хранения длины подстроки, которую мы найдем в этой позиции.
Для «p» максимальная подстрока без повторяющихся символов — «p». Итак, наш массив будет выглядеть так:
Теперь возьмем «pw». Сначала мы сравниваем «w» и «p». Они не совпадают.
Мы уже знаем, что максимальная подстрока, оканчивающаяся на «p», равна «p».
Следовательно, максимальная подстрока, оканчивающаяся на «w», равна «pw».
Для «pww» мы сначала сравниваем «w» (idx. 2) с «w» (idx. 1). Это повторяющиеся символы, поэтому мы не можем включать саму ‘w’ (idx. 1).
Следовательно, максимальная подстрока, оканчивающаяся на «w» (idx. 2), равна «w».
Для «pwwk» мы сравниваем «k» с «w» (idx. 2). Они не совпадают.
Мы уже знаем, что максимальная подстрока, оканчивающаяся на «w» (idx. 2) без повторяющихся символов, — это только «w». Кроме того, «k» отсутствует в «w».
Таким образом, максимальная подстрока, оканчивающаяся на «k», может быть только «wk».
Точно так же для «pwwke» мы можем сравнить «e» с «k», и они не совпадают.
Мы знаем, что максимальная подстрока, оканчивающаяся на «k», равна «wk». Кроме того, «е» отсутствует в «wk».
Следовательно, максимальная подстрока, оканчивающаяся здесь, — «wke».
И, наконец, для «pwwkew» мы можем сравнить «w» (индекс 5) с «e», и они не совпадают.
Мы знаем, что на «e» максимальная подстрока, оканчивающаяся на «wke». Но «w» уже присутствует в «wke», поэтому мы можем взять только все символы справа от этого «w» (индекс 2).
Это означает, что максимальная подстрока, оканчивающаяся здесь, будет только «kew» («ke» + «w»).
Теперь, когда мы просмотрели всю строку, мы знаем максимальную подстроку, которая может быть без повторяющихся символов, заканчивающихся в каждой позиции.
Максимальное значение, которое мы имеем в нашем массиве, равно 3 для подстрок «wke» и «kew».
Итак, длина «Самой длинной подстроки без повторяющихся символов» в «pwwkew» равна 3.
И вот как вы решаете проблему «Самая длинная подстрока без повторяющихся символов».
Если вы заинтересованы в решении других проблем, подписывайтесь на 60 Days of Coding и присоединяйтесь ко мне в этом путешествии.
Если вы хотите, чтобы я решил и объяснил какие-либо проблемы, добавьте их в комментарии вместе со ссылкой на описание проблемы.
Увидимся завтра!
Ваше здоровье!
