Python | LeetCode
Задача: 1062. Longest Repeating Substring
Сложность: medium
Дана строка s. Вернуть длину самой длинной повторяющейся подстроки. Если повторяющаяся подстрока отсутствует, вернуть 0.
Пример:
Input: s = "abcd"
Output: 0
Explanation: There is no repeating substring.
👨💻 Алгоритм:
1⃣Перемещайте скользящее окно длиной L по строке длиной N.
2⃣Проверьте, находится ли строка в скользящем окне в хэш-наборе уже виденных строк. Если да, то повторяющаяся подстрока находится здесь. Если нет, сохраните строку из скользящего окна в хэш-наборе.
3⃣Очевидный недостаток этого подхода — большое потребление памяти в случае длинных строк.
😎 Решение:
class Solution:
def search(self, L, n, S):
seen = set()
for start in range(n - L + 1):
tmp = S[start:start + L]
if tmp in seen:
return start
seen.add(tmp)
return -1
def longestRepeatingSubstring(self, S):
n = len(S)
left, right = 1, n
while left <= right:
L = left + (right - left) // 2
if self.search(L, n, S) != -1:
left = L + 1
else:
right = L - 1
return left - 1
Ставь 👍 и забирай 📚 Базу знаний
5 · 803 ·