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

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

Пример:

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

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

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

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

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

😎 Решение:

public class Solution {
    public string LongestDupSubstring(string s) {
        int left = 1, right = s.Length;
        string result = "";
        while (left < right) {
            int mid = (left + right) / 2;
            string dup = Search(s, mid);
            if (dup != null) {
                result = dup;
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return result;
    }

    private string Search(string s, int length) {
        HashSet<string> seen = new HashSet<string>();
        for (int i = 0; i <= s.Length - length; i++) {
            string sub = s.Substring(i, length);
            if (seen.Contains(sub)) {
                return sub;
            }
            seen.Add(sub);
        }
        return null;
    }
}

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