Minimum Cuts for Palindrome Partitioning

You are given a string s. Your task is to partition the string into substrings such that each substring is a palindrome. A palindrome is a string that reads the same forward and backward. The goal is to make these partitions with the minimum number of cuts.

Formally, let \( s[0\ldots n-1] \) be the input string. You need to find the minimum number of cuts required so that every substring in the partition is a palindrome.

For example:

• If s = "a", no cuts are needed.
• If s = "ab", one cut is required to partition it into "a" and "b".
• If s = "aab", one optimal partition is "aa" and "b", so only 1 cut is needed.

Solve the problem using dynamic programming with a time complexity of \(O(n^2)\) where \(n\) is the length of the string. Use the following hint: define an array \(dp\) where \(dp[i]\) represents the minimum cuts needed for the substring \(s[0\ldots i]\).

inputFormat

The input consists of a single string s consisting of lowercase and/or uppercase letters. The string is provided via standard input.

outputFormat

Output a single integer representing the minimum number of cuts required to partition the string such that every substring is a palindrome. The result should be printed to standard output.

a

0