Задача: 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 {
    search(L, n, S) {
        const seen = new Set();
        for (let start = 0; start <= n - L; ++start) {
            const tmp = S.substring(start, start + L);
            if (seen.has(tmp)) return start;
            seen.add(tmp);
        }
        return -1;
    }

    longestRepeatingSubstring(S) {
        const n = S.length;
        let left = 1, right = n;
        while (left <= right) {
            const L = left + Math.floor((right - left) / 2);
            if (this.search(L, n, S) !== -1) {
                left = L + 1;
            } else {
                right = L - 1;
            }
        }
        return left - 1;
    }
}

Ставь 👍 и забирай 📚 Базу знаний