Triple Palindrome Partition

Hard

Given a string of lowercase characters, determine whether it is possible to divide the string into exactly three contiguous, non-empty segments such that each segment reads the same forwards and backwards (forming a palindrome). A palindrome is defined as a sequence of characters that is identical when read from left to right or from right to left. Examples include "a", "aa", "aba", "abcba", and "racecar". Your task is to analyze the input string and return true if such a triple-partition exists where all three resulting substrings are palindromes, otherwise return false . For instance, the string "abcbdd" can be split into "a" + "bcb" + "dd", where "a" is a single-character palindrome, "bcb" is a three-character palindrome, and "dd" is a two-character palindrome. Thus, a valid partition exists. Note that you must use every character in the string exactly once, and each of the three parts must contain at least one character.

Example 1

Input

s = "abcbdd"

Output

true

Explanation

The string can be partitioned as "a" + "bcb" + "dd". Here, "a" is a single-character palindrome (all single characters are palindromes), "bcb" reads the same forwards and backwards, and "dd" is a two-character palindrome. Therefore, a valid triple-palindrome partition exists.

Example 2

Input

s = "bcbddxy"

Output

false

Explanation

No matter how we try to split this string into three parts, at least one part will not be a palindrome. For instance, "bcb" + "dd" + "xy" fails because "xy" ≠ "yx". All possible triple partitions have been exhausted and none satisfy the condition.

Example 3

Input

s = "aaa"

Output

true

Explanation

The string can be partitioned as "a" + "a" + "a". Each single character is inherently a palindrome. This represents the minimal valid case where the string has exactly three characters.

Constraints

3 ≤ s.length ≤ 2000
s consists only of lowercase English letters (a-z).
The string must be partitioned into exactly three non-empty parts.