Задача: 1044. Longest Duplicate Substring
Сложность: hard

Учитывая строку s, рассмотрите все дублированные подстроки: (смежные) подстроки s, которые встречаются 2 или более раз.Вхождения могут перекрываться. Верните любую дублированную подстроку, которая имеет наибольшую возможную длину.Если в s нет дублирующейся подстроки, ответом будет "".

Пример:

Input: s = "banana"
Output: "ana"

👨‍💻 Алгоритм:

1⃣Использование двоичного поиска для определения длины дублированной подстроки:
Двоичный поиск используется для поиска максимальной длины дублированной подстроки.

2⃣Использование хеширования для проверки наличия дублированной подстроки определенной длины:
Для каждой длины, определенной двоичным поиском, используем хеширование для поиска подстрок.

3⃣Хеширование с помощью функции rolling hash:
Rolling hash позволяет быстро вычислять хеши подстрок фиксированной длины и сравнивать их для поиска дубликатов.

😎 Решение:

function longestDupSubstring(s) {
    function search(len) {
        let seen = new Set();
        for (let i = 0; i <= s.length - len; i++) {
            let sub = s.slice(i, i + len);
            if (seen.has(sub)) {
                return sub;
            }
            seen.add(sub);
        }
        return "";
    }

    let left = 1, right = s.length;
    let result = "";
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        let dup = search(mid);
        if (dup) {
            result = dup;
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return result;
}

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