Задачи на строки на собеседовании: разбор типовых

Коротко

Ключевая мысль: строка — это массив символов, и большинство приёмов оттуда переносятся напрямую.

Палиндромы

Проверка палиндрома

def is_palindrome(s: str) -> bool:
    left, right = 0, len(s) - 1

    while left < right:
        # пропускаем всё, что не буква и не цифра
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1

        if s[left].lower() != s[right].lower():
            return False

        left += 1
        right -= 1

    return True

Соблазн написать s == s[::-1] велик, но так вы тратите O(n) памяти и не показываете владение двумя указателями. На интервью лучше развёрнутый вариант — а однострочник упомянуть как альтернативу.

Ловушка: внутренние while тоже должны проверять left < right, иначе на строке из одних знаков препинания указатели разъедутся.

Самая длинная палиндромная подстрока

Классика посложнее. Идея «расширение от центра»: каждый символ и каждый промежуток между символами может быть центром.

def longest_palindrome(s: str) -> str:
    if not s:
        return ''

    start, length = 0, 1

    def expand(left: int, right: int) -> None:
        nonlocal start, length
        while left >= 0 and right < len(s) and s[left] == s[right]:
            if right - left + 1 > length:
                start, length = left, right - left + 1
            left -= 1
            right += 1

    for i in range(len(s)):
        expand(i, i)            # нечётная длина
        expand(i, i + 1)        # чётная длина

    return s[start:start + length]

O(n²) по времени, O(1) по памяти. Существует линейный алгоритм Манакера, но на интервью его не ждут — достаточно упомянуть, что он есть.

Обязательно обработайте оба случая центра. Забыть чётный — самая частая ошибка: строка abba не найдётся.

Анаграммы

Проверка анаграммы

from collections import Counter

def is_anagram(s: str, t: str) -> bool:
    return Counter(s) == Counter(t)

Или вручную, если просят без библиотек:

def is_anagram_manual(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False

    counts = {}
    for ch in s:
        counts[ch] = counts.get(ch, 0) + 1

    for ch in t:
        if ch not in counts:
            return False
        counts[ch] -= 1
        if counts[ch] == 0:
            del counts[ch]

    return not counts

Проверка длин в начале — не оптимизация, а необходимость: без неё abc и abcc дадут неверный результат в некоторых реализациях.

Альтернатива через сортировку — O(n log n), но короче. Проговорите обе и обоснуйте выбор.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

Группировка анаграмм

from collections import defaultdict

def group_anagrams(words: list[str]) -> list[list[str]]:
    groups = defaultdict(list)
    for word in words:
        key = ''.join(sorted(word))     # канонический вид
        groups[key].append(word)
    return list(groups.values())

Ключевая идея: привести к каноническому виду и использовать как ключ. Приём переносится на множество задач — везде, где нужно группировать «одинаковое с точностью до чего-то».

Альтернативный ключ, если алфавит маленький: кортеж из 26 счётчиков. Это O(n·k) вместо O(n·k log k), но код длиннее.

Скользящее окно по символам

Самая длинная подстрока без повторов

def length_of_longest(s: str) -> int:
    window = set()
    left = 0
    best = 0

    for right, ch in enumerate(s):
        while ch in window:
            window.discard(s[left])
            left += 1
        window.add(ch)
        best = max(best, right - left + 1)

    return best

Вложенный while не портит сложность: указатель left за всю работу проходит строку один раз. Итого O(n) — это нужно проговорить, иначе интервьюер решит, что вы не понимаете свою же оценку.

Замена символов с ограничением

def character_replacement(s: str, k: int) -> int:
    counts = {}
    left = 0
    max_freq = 0
    best = 0

    for right, ch in enumerate(s):
        counts[ch] = counts.get(ch, 0) + 1
        max_freq = max(max_freq, counts[ch])

        # символов на замену больше, чем разрешено
        while right - left + 1 - max_freq > k:
            counts[s[left]] -= 1
            left += 1

        best = max(best, right - left + 1)

    return best

Ключевая строка — right - left + 1 - max_freq: длина окна минус самая частая буква и есть количество замен.

Поиск подстроки

На интервью обычно достаточно упомянуть варианты:

Наивный — O(n·m), для коротких строк приемлемо.

KMP — O(n + m), через префикс-функцию. Реализовать по памяти на интервью тяжело, но объяснить идею («не возвращаемся назад в тексте, используем совпавший префикс») стоит уметь.

Хеширование (Рабин-Карп) — O(n + m) в среднем, проще пишется, хорош при поиске нескольких образцов.

Если задача звучит как «найдите вхождение подстроки», обычно ждут либо встроенную функцию, либо наивный вариант с обсуждением, что бывает лучше.

Подводные камни

Строки неизменяемы

В Python и Java конкатенация в цикле создаёт новую строку каждый раз:

# O(n²) — каждая конкатенация копирует всё
result = ''
for ch in text:
    result += ch

# O(n)
result = ''.join(text)

Это одна из самых частых скрытых ошибок сложности. В Java та же история с String против StringBuilder.

Unicode ломает интуицию

s = 'ёжик'
len(s)              # 4 — здесь всё хорошо

emoji = '👨‍👩‍👧'
len(emoji)          # 5 — один видимый символ, пять кодовых точек

Если в задаче про строки могут быть эмодзи или комбинирующие символы, разворот строки посимвольно их сломает. На интервью достаточно спросить, гарантирован ли ASCII — сам вопрос производит хорошее впечатление.

Регистр и локаль

'I'.lower() в турецкой локали даёт не то, что вы ожидаете. Экзотика, но упомянуть при обсуждении крайних случаев можно.

Пустая строка

Проверяйте всегда. s[0] на пустой строке падает, а условие про это часто молчит.

Что уточнять у интервьюера

• Только ASCII или возможен Unicode?
• Учитывать ли регистр?
• Что делать с пробелами и пунктуацией?
• Гарантирована ли непустая строка?
• Можно ли использовать встроенные функции языка?

Последний вопрос особенно важен: разрешён ли Counter, sorted, str.find — это меняет решение принципиально.

Что запомнить

• Строка — массив символов, приёмы для массивов переносятся напрямую.
• Палиндром — два указателя, не срез с разворотом.
• В задачах на палиндромные подстроки обрабатывайте оба типа центра.
• Анаграммы — счётчик символов; группировка — канонический ключ через сортировку.
• Конкатенация в цикле даёт скрытый квадрат: используйте join или StringBuilder.
• Спросите про Unicode и регистр — это ценится отдельно.