Problem Description

Given a string, find the minimum number of cuts needed to partition it such that every substring is a palindrome. For example, "aab" needs 1 cut to become "aa|b".

Input Format

A single string containing lowercase letters.

Output Format

Minimum number of cuts needed for palindrome partitioning.

Constraints

• 1 ≤ string length ≤ 500

• String contains only lowercase letters

• Each partition must be a palindrome

• Find minimum cuts, not the actual partitions

• Use dynamic programming for efficiency

Sample Input/Output

Explanation

String "aab" can be partitioned as "aa|b" with 1 cut. Both "aa" and "b" are palindromes.