Сложность: medium
Дана строка s. Вернуть длину самой длинной повторяющейся подстроки. Если повторяющаяся подстрока отсутствует, вернуть 0.
Пример:
Input: s = "abcd"
Output: 0
Explanation: There is no repeating substring.
👨💻 Алгоритм:
1⃣Перемещайте скользящее окно длиной L по строке длиной N.
2⃣Проверьте, находится ли строка в скользящем окне в хэш-наборе уже виденных строк. Если да, то повторяющаяся подстрока находится здесь. Если нет, сохраните строку из скользящего окна в хэш-наборе.
3⃣Очевидный недостаток этого подхода — большое потребление памяти в случае длинных строк.
😎 Решение:
class Solution {
func search(_ L: Int, _ n: Int, _ S: String) -> Int {
var seen = Set<String>()
for start in 0...(n - L) {
let tmp = String(S[S.index(S.startIndex, offsetBy: start)..<S.index(S.startIndex, offsetBy: start + L)])
if seen.contains(tmp) { return start }
seen.insert(tmp)
}
return -1
}
func longestRepeatingSubstring(_ S: String) -> Int {
let n = S.count
var left = 1, right = n
while left <= right {
let L = left + (right - left) / 2
if search(L, n, S) != -1 {
left = L + 1
} else {
right = L - 1
}
}
return left - 1
}
}Ставь 👍 и забирай 📚 Базу знаний