Split a String into Exactly Three Palindromes

## Problem Determine whether a string can be split into exactly three nonempty contiguous substrings, each of which is a palindrome. Return a Boolean. A palindrome reads the same from left to right and right to left. The three substrings must cover the entire input without overlap or reordering. ### Function Contract Implement `canSplitIntoThreePalindromes(s)`. ### Constraints & Assumptions - `3 <= len(s) <= 2,000`. - `s` contains lowercase English letters. - Exactly two cut positions must be chosen. - A one-character substring is a palindrome. ### Clarifying Questions to Ask - Must all three pieces be nonempty? Yes. - Are deletions allowed? No. - Does the function need to return the split? No, only whether one exists. - Can the same character be shared by two pieces? No. ```hint Precompute interval palindromes Build a table in which `pal[left][right]` records whether that closed interval is a palindrome. Then testing a pair of cuts is constant time. ``` ```hint Leave room for every piece The first cut may follow positions `0` through `n-3`; the second may follow the next position through `n-2`. ``` ### Examples ```text "abcbdd" -> true ("a" | "bcb" | "dd") "bcbddxy" -> false "aaa" -> true ("a" | "a" | "a") ``` ### Evaluation Focus - Uses exactly three nonempty contiguous pieces. - Fills the palindrome table in a dependency-safe order. - Checks valid cut ranges without off-by-one errors. - Runs in `O(n^2)` time and `O(n^2)` space, or provides a correct equivalent optimization. ### Extensions to Discuss 1. How would you return one valid pair of cut positions? 2. How would the problem change for exactly `p` palindromic pieces? 3. Can the space usage be reduced while keeping quadratic time?