Самая длинная общая подстрока двух строк

Условие задачи

Напишите функцию `longest_common_substring(s1, s2)`, возвращающую длину самой длинной общей подстроки (не подпоследовательности — символы должны идти подряд). Например, "ABCDEF" и "ZBCDF" → "BCD" длины 3.

Темы

algorithms python strings dp

Подсказки

• Это динамическое программирование: dp[i][j] = длина общей подстроки заканчивающейся в s1[i-1] и s2[j-1]
• Если символы совпали: dp[i][j] = dp[i-1][j-1] + 1, иначе 0
• Не путай с longest common subsequence (там символы могут не подряд)

Что проверяет эта задача

Задача «Самая длинная общая подстрока двух строк» учит решать алгоритмические задачи на Python: оценивать сложность по времени и памяти и выбирать подходящую структуру данных. Такие задачи дают на собеседованиях в Сбер и других IT-компаниях. Уровень сложный — проверяет глубину и умение собрать решение из нескольких приёмов.

Как подступиться к решению

Сначала разбери условие и формат входа-выхода, прикинь крайние случаи (пустой ввод, дубли, NaN). Затем выбери структуру данных и собери решение по шагам — начни с простого рабочего варианта, потом оптимизируй сложность. Код пишешь и запускаешь прямо в браузере: Python-тренажёр исполняет его через Pyodide (pandas, numpy, scipy) и проверяет результат автоматически.

На собеседовании по Python для аналитика ценят чистый читаемый код, корректную обработку крайних случаев (пустой ввод, дубли, None) и умение вслух оценить сложность по времени и памяти. Часто просят не просто решить, а разобрать альтернативные подходы и показать, где наивное решение сломается на большом объёме данных.

Прокачать Python для аналитики — бесплатный курс «Pandas с нуля» и Python-тренажёр.

Открыть задачу в тренажёре → ← Все Python-задачи