Partition a String into Exactly Three Palindromic Substrings

Given a string s, determine whether it can be partitioned into exactly three non-empty contiguous substrings, where every substring is a palindrome. Requirements: Describe a direct approach that enumerates split positions. Optimize palindrome checks by precomputing palindromic substrings with dynamic programming. Output whether such a partition exists. Input Format One string s containing lowercase English letters. Output Format Print true if possible; otherwise print false. Constraints 3 <= len(s) <= 2000 Example Input abcbdd Output true