Given a string s of lowercase English letters, determine whether s can be cut into three non-empty consecutive substrings such that every one of them is a palindrome. Return true if such a split exists and false otherwise.
A palindrome is a string that reads the same forwards and backwards.
Examples
Example 1
Input: s = "abcbdd"
Output: true
Explanation: "abcbdd" = "a" + "bcb" + "dd", and all three parts are palindromes.
Example 2
Input: s = "bcbddxy"
Output: false
Explanation: No way of cutting s into three parts yields three palindromes.
Constraints
3≤s.length≤2000
s consists of lowercase English letters.
Examples
Example 1
Input
s = "abcbdd"
Output
true
Example 2
Input
s = "bcbddxy"
Output
false
Loading editor...
Click "Run" to test with sample cases or "Submit" to run all tests.