Задача с собеседования в TCS

Дана строка s, верните true, если возможно разделить её на 3 непустые палиндромные подстроки. В противном случае верните false.
Строка называется палиндромом, если в перевёрнутом виде она остаётся той же самой строкой.

Пример 1:
Input: s = "abcbdd"
Output: true
Explanation: "abcbdd" = "a" + "bcb" + "dd", все три подстроки являются палиндромами.

Пример 2:
Input: s = "bcbddxy"
Output: false
Explanation: s нельзя разделить на 3 палиндрома.

Ограничения:
3 <= s.length <= 2000
s состоит только из строчных английских букв.

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Задача помечена тегом "Dynamic Programming". Реализуем восходящее dp для проверки подстроки на палиндромность: заполняем таблицу от коротких подстрок к длинным, используя результаты для маленьких подстрок при вычислении больших. Запоминаем булево значение для каждой пары (i, j) и используем для получения ответа за O(1):

- Создаём таблицу размером n * n, заполненную False, где dp[i][j] - ответ, является ли подстрока от индекса i до j палиндромом;
- Заполняем таблицу вложенным циклом, двигаясь переменной i от конца строки к началу, а переменной j - от i вправо, строя подстроки по возрастанию длины. Таким образом, направление i и j гарантирует, что когда вычисляем dp[i][j], ответ для середины подстроки (dp[i+1][j-1]) уже готов.
- Проверяем подстроку на палиндромность:
Если крайние символы равны (s[i] == s[j]), то подстрока является палиндромом при выполнении хотя бы одного из двух условий:
- подстрока состоит из одного или двух символов (j - i <= 1) => подстрока - палиндром;
- внутренняя часть подстроки (dp[i+1][j-1]) - палиндром => вся подстрока - палиндром, так как крайние символы равны.

Теперь имея результаты табличных вычислений, перебираем две точки разреза, которые делят строку на три части: s[0..i] + s[i+1..j] + s[j+1..n-1]
i - индекс конца первого палиндрома
j - индекс конца второго палиндрома
Проходим внешним циклом i от 0, оставляя как минимум по одному символу для второго и третьего палиндромов:
- если префикс (dp[0][i]) - палиндром, переходим ко внутреннему циклу от i+1 до предпоследнего индекса (оставляем хотя бы один символ для третьего палиндрома):
- если второй отрезок - палиндром и третий отрезок - палиндром => можно разбить на 3 палиндрома => возвращаем True.
Иначе возвращаем False.

Сложность
O(n^2) - по времени (строим дп-таблицу за n^2, перебираем разрезы за n^2)
O(n^2) - по памяти (храним дп-таблицу)

Код
class Solution:
def checkPartitioning(self, s: str) -> bool:
n = len(s)

dp = [[False] * n for _ in range(n)]

for i in range(n - 1, -1, -1):
for j in range(i, n):
if s[i] == s[j]:
dp[i][j] = (j - i <= 1) or dp[i+1][j-1]

for i in range(n - 2):
if dp[0][i]:
for j in range(i + 1, n - 1):
if dp[i + 1][j] and dp[j + 1][n - 1]:
return True

return False

@algoses