**Problem :- **

Splitting a String into minimum number of **palindromes**.

Given a string, find the minimum no. of palidromes into which the string can be broken.

Consider the string **"civic"** ( String is Palindrome by itself, so min no. of palindromes = **1** )

The string **"abcde"** cannot be splitted into less than **5** palindromes ( each character is a palindrome )

Consider the string **"civicacaramanamaracacammacdeified"**.

It can be broken into 4 palindromes **" civic " + " acaramanamaraca " + " cammac " + " deified "**

**Solution :- **

Suppose the size of the string is **n**.

We maintain a 2D array **palins [ n ][ n ]** where **palins [ i ][ j ]** stores the minimum number of palindromes in the
string **str [ i ... j ]** i.e from index **' i '** to index **' j '** of the string. So, the final solution of
breaking the string of size **n** into minimum no. of palindromes is given by **palins [ 0 ][ n - 1 ]**.

Let us determine the structure of the optimal solution.

Let **palins ( i , j )** denotes the min no. of palindromes in the string **str ( i ... j )**.

We will try to break the string at all possible positions **k** such that ** i <= k < j** and sum up the minimum no. of
palindromes in **palins ( i , k )** and **palins ( k , j )**.

Thus, the structure of optimal solution is determined recursively as :

**palins ( i , j ) = palins ( i , k ) + palins ( k , j ) for all i <= k < j**

Finally, **palins ( 0 , n - 1 )** gives the required solution. See the implementation below.

**#include<iostream>
#include<cstring>**
**using namespace** std;
*// check if a string is palindrome, given the start and end index of the string*
**bool** isPalindrome(**char** str[], **int** i, **int** j) {
**while** (i < j) {
**if** (str[i++] != str[j--])
**return false**;
}
**return true**;
}
*/* Find the minimum no. of palindromes in the input string i.e the
string has to broken down into min. no. of palindromes
Suppose palins[i][j] -> min no. of palindromes in the string str[i...j]
Then, palins[0][n-1] is the final solution
Standard Recursive Solution :-
palins(i,j) = min(palins(i,k) + palins(k,j)) for i <= k < j
*/*
**int** minPalindromes(**char** str[]) {
**int** i, j, k;
**int** substr_size; *//substring size*
**int** n = strlen(str);
*// Matrix where cell (i,j) stores the minimum no. of palindromes in str[i...j] *
**int** palins[n][n];
*// iterating over all possible substring sizes*
**for** (substr_size = 1; substr_size <= n; substr_size++) {
*// 'i' and 'j' tracks the start and end index of the current substring*
**for** (i = 0; i <= n - substr_size; i++) {
j = i + substr_size - 1;
**if** (isPalindrome(str, i, j)) {
*// substring is a palindrome*
palins[i][j] = 1;
}
**else** {
*// search for palindromes within the substring
// worst case (min. no of palindromes = length of the substring)
// each character is a palindrome *
palins[i][j] = substr_size;
*// find min no. of palindromes within substring*
**for** (k = i; k < j; k++) {
*// try splitting substring at each position*
**int** sum = palins[i][k] + palins[k+1][j];
**if** (sum < palins[i][j])
palins[i][j] = sum;
}
}
}
}
*// return min no. of palindromes in the input string*
**return** palins[0][n-1];
}
*// main*
**int** main() {
**char** str[] = "civicacaramanamaracacammacdeified";
*//civic + acaramanamaraca + cammac + deified (4 palindromes)*
**int** min_palin = minPalindromes(str);
cout<<"\nMinimum no. of palindromes :: "<<min_palin;
cout<<endl;
**return** 0;
}