Уникальные подстроки длины n

Уникальные подстроки длины n

Проблема

Найти все уникальные подстроки (substring) фиксированной длины в строке. Это полезно для поиска повторяющихся паттернов, анализа текста и обнаружения дублирования.

1. Наивное решение со скользящим окном

def unique_substrings(s: str, n: int) -> set[str]:
    """
    Найти все уникальные подстроки длины n.
    
    Временная сложность: O(m * n), где m = len(s) - n + 1
    Пространственная: O(m * n) для хранения подстрок
    """
    if n > len(s):
        return set()
    
    unique = set()
    for i in range(len(s) - n + 1):
        unique.add(s[i:i+n])
    return unique

# Примеры
print(unique_substrings("abcabc", 3))  # {'abc', 'bca', 'cab'}
print(unique_substrings("aaaa", 2))    # {'aa'}
print(unique_substrings("hello", 2))   # {'he', 'el', 'll', 'lo'}

Особенности:

• Скользящее окно проходит по строке один раз O(m)
• Каждый срез s[i:i+n] — это O(n) операция (создание новой строки)
• Set автоматически удаляет дубликаты
• Временная сложность: O(m * n) из-за создания подстрок

2. Оптимизация с использованием хеша (rolling hash)

Для длинных строк или больших n можно использовать rolling hash вместо создания подстрок:

def unique_substrings_hash(s: str, n: int) -> set[str]:
    """
    Оптимизированное решение с rolling hash.
    Избегаем создания подстрок в памяти.
    
    Временная сложность: O(m) вместо O(m * n)
    Пространственная: O(m)
    """
    if n > len(s):
        return set()
    
    # BASE и MOD для хеша
    BASE = 256
    MOD = 10**9 + 7
    
    # Вычисляем BASE^(n-1) % MOD один раз
    pow_base = pow(BASE, n - 1, MOD)
    
    # Вычисляем хеш первого окна
    current_hash = 0
    for i in range(n):
        current_hash = (current_hash * BASE + ord(s[i])) % MOD
    
    hashes = {current_hash}
    substrings = {s[0:n]}
    
    # Rolling hash для остальных окон
    for i in range(1, len(s) - n + 1):
        # Удаляем первый символ и добавляем новый
        current_hash = (
            (current_hash - ord(s[i-1]) * pow_base) % MOD +
            (ord(s[i+n-1]) * pow(BASE, n-1, MOD))
        ) % MOD
        current_hash = (current_hash % MOD + MOD) % MOD
        
        # Проверяем наличие хеша
        if current_hash not in hashes:
            hashes.add(current_hash)
            substrings.add(s[i:i+n])
        else:
            # Collision — проверяем, что это не false positive
            if s[i:i+n] not in substrings:
                substrings.add(s[i:i+n])
    
    return substrings

3. Простое и читаемое решение

def unique_substrings_simple(s: str, n: int) -> set[str]:
    """
    Самое простое решение — просто и понятно.
    Использует встроенные функции Python.
    """
    return {s[i:i+n] for i in range(len(s) - n + 1)} if n <= len(s) else set()

# Примеры
print(unique_substrings_simple("abcabc", 3))
print(unique_substrings_simple("aaaa", 2))

Это one-liner версия — самая читаемая и достаточна для большинства случаев.

4. Поиск ВСЕХ повторяющихся подстрок

def find_duplicate_substrings(s: str, n: int) -> set[str]:
    """
    Найти подстроки длины n, которые встречаются БОЛЬШЕ ОДНОГО раза.
    Используем rolling hash для эффективности.
    """
    if n > len(s):
        return set()
    
    seen = set()
    duplicates = set()
    
    for i in range(len(s) - n + 1):
        substring = s[i:i+n]
        if substring in seen:
            duplicates.add(substring)
        seen.add(substring)
    
    return duplicates

# Примеры
print(find_duplicate_substrings("abcabcab", 3))  # {'abc', 'cab'}
print(find_duplicate_substrings("aaaa", 2))      # {'aa'}

5. Версия, которая также возвращает позиции

def unique_substrings_with_positions(s: str, n: int) -> dict[str, list[int]]:
    """
    Возвращает уникальные подстроки и их позиции в строке.
    """
    result = {}
    
    for i in range(len(s) - n + 1):
        substring = s[i:i+n]
        if substring not in result:
            result[substring] = []
        result[substring].append(i)
    
    return result

# Пример
print(unique_substrings_with_positions("abcabc", 3))
# {'abc': [0, 3], 'bca': [1], 'cab': [2]}

6. Версия для очень больших строк (генератор)

def unique_substrings_generator(s: str, n: int):
    """
    Для очень больших строк — генератор для экономии памяти.
    Возвращает подстроки по одной.
    """
    seen = set()
    
    for i in range(len(s) - n + 1):
        substring = s[i:i+n]
        if substring not in seen:
            seen.add(substring)
            yield substring

# Использование
for substring in unique_substrings_generator("abcabcab", 3):
    print(substring)  # abc, bca, cab

Сравнение подходов

Практический совет

Для собеседования:

# Первый вариант — простой и правильный
def unique_substrings(s: str, n: int) -> set[str]:
    return {s[i:i+n] for i in range(len(s) - n + 1)} if n <= len(s) else set()

Этого достаточно в 99% случаев. Если интервьюер попросит оптимизацию — предложите rolling hash.

Граничные случаи

# n > len(s)
unique_substrings("ab", 5)  # set()

# n == len(s)
unique_substrings("abc", 3)  # {'abc'}

# n == 1
unique_substrings("aaa", 1)  # {'a'}

# Пустая строка
unique_substrings("", 1)  # set()

# n == 0
unique_substrings("abc", 0)  # set() или error