Задача: 1062. Longest Repeating Substring
Сложность: medium

Дана строка s. Вернуть длину самой длинной повторяющейся подстроки. Если повторяющаяся подстрока отсутствует, вернуть 0.

Пример:

Input: s = "abcd"
Output: 0
Explanation: There is no repeating substring.

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

1⃣Перемещайте скользящее окно длиной L по строке длиной N.

2⃣Проверьте, находится ли строка в скользящем окне в хэш-наборе уже виденных строк. Если да, то повторяющаяся подстрока находится здесь. Если нет, сохраните строку из скользящего окна в хэш-наборе.

3⃣Очевидный недостаток этого подхода — большое потребление памяти в случае длинных строк.

😎 Решение:

public class Solution {
    public int Search(int L, int n, string S) {
        var seen = new HashSet<string>();
        for (int start = 0; start <= n - L; ++start) {
            string tmp = S.Substring(start, L);
            if (seen.Contains(tmp)) return start;
            seen.Add(tmp);
        }
        return -1;
    }

    public int LongestRepeatingSubstring(string S) {
        int n = S.Length;
        int left = 1, right = n;
        while (left <= right) {
            int L = left + (right - left) / 2;
            if (Search(L, n, S) != -1) {
                left = L + 1;
            } else {
                right = L - 1;
            }
        }
        return left - 1;
    }
}

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