Задача с собеседования в 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 можно разбить на 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