Partition a String into Exactly Three Palindromic Substrings

You are given a string s made only of lowercase English letters. Decide whether s can be split into exactly three non-empty contiguous substrings so that all three of those substrings are palindromes. A straightforward solution is to try every possible pair of split positions. To make those checks efficient, first precompute which intervals are palindromic using dynamic programming, for example with a boolean table isPal[i][j] that records whether the substring from index i…