Problem Statement

Given a string, we want to cut it into pieces such that each piece is a palindrome. Write a function to return the minimum number of cuts needed.

Example 1:

Input: "abdbca" Output: 3 Explanation: Palindrome pieces are "a", "bdb", "c", "a". 

Example 2:

Input: = "cddpd" Output: 2 Explanation: Palindrome pieces are "c", "d", "dpd". 

Example 3:

Input: = "pqr" Output: 2 Explanation: Palindrome pieces are "p", "q", "r". 

Example 4:

Input: = "pp" Output: 0 Explanation: We do not need to cut, as "pp" is a palindrome.