# Palindrome Partitioning Problem in C++

«
»
This C++ Program Solves Palindrome Partitioning Problem.

Here is source code of the C++ Program to solve Palindrome Partitioning Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

1. `/*`
2. ` * C++ Program to Solve Palindrome Partitioning Problem`
3. ` */`
4. `#include <iostream>`
5. `#include <cstdio>`
6. `#include <cstring>`
7. `#include <climits>`
8. `#include <cstring>`
9. `#include <cstdlib>`
10. `using namespace std;`
11. ` `
12. `// get minimum of two integers`
13. `int min (int a, int b)`
14. `{`
15. `    return (a < b)? a : b;`
16. `}`
17. ` `
18. `/* Returns the minimum number of cuts needed to partition a string`
19. ` * such that every part is a palindrome`
20. ` */`
21. `int minPalPartion(char *str)`
22. `{`
23. `    int n = strlen(str);`
24. `    int C[n][n];`
25. `    bool P[n][n];`
26. `    int i, j, k, L;`
27. `    for (i = 0; i < n; i++)`
28. `    {`
29. `        P[i][i] = true;`
30. `        C[i][i] = 0;`
31. `    }`
32. `    for (L = 2; L <= n; L++)`
33. `    {`
34. `        for (i = 0; i < n - L + 1; i++)`
35. `        {`
36. `            j = i + L - 1;`
37. `            if (L == 2)`
38. `                P[i][j] = (str[i] == str[j]);`
39. `            else`
40. `                P[i][j] = (str[i] == str[j]) && P[i + 1][j - 1];`
41. `            if (P[i][j] == true)`
42. `                C[i][j] = 0;`
43. `            else`
44. `            {`
45. `                C[i][j] = INT_MAX;`
46. `                for (k = i; k <= j - 1; k++)`
47. `                    C[i][j] = min (C[i][j], C[i][k] + C[k + 1][j] + 1);`
48. `            }`
49. `        }`
50. `    }`
51. `    return C[0][n-1];`
52. `}`
53. ` `
54. `// Main`
55. `int main()`
56. `{`
57. `    char str[] = "ababbbabbababa";`
58. `    cout<<"Min cuts needed for Palindrome Partitioning is: "<<minPalPartion(str);`
59. `    cout<<endl;`
60. `    return 0;`
61. `}`

```\$ g++ palindrome_partitioning.cpp
\$ a.out

Min cuts needed for Palindrome Partitioning is: 3

------------------
(program exited with code: 1)

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.