Palindrome Partitioning II in C++

Suppose we have a string s, we have to find the number of cuts needed to divide this string into different substring and each part is a palindrome. So if the string is like “ababba”, then this will take 2 cuts. [aba|bb|a]

To solve this, we will follow these steps −

• n := number of characters in the string s

• create one array called res of size n + 1

• res[n] := -1

• for i in range n – 1 down to 0

  • res[i] := n – i – 1

  • for j in range i to n

    • if substring of a, from index i, to j – i is a palindrome, then

      • res[i] := min of res[i] and 1 + res[j + 1]

• return res[0]

Example

Let us see the following implementation to get a better understanding −

 Live Demo

#include <bits/stdc++.h> using namespace std; bool isPalindrome(string A) {    int left = 0;    int right = A.size()-1;    while(left < right) {       if(A[left] != A[right]) {          return 0;       }       left++;       right--;    }    return 1; } int solve(string A) {    int n = A.size();    vector<int>result(n+1);    result[n] = -1;    for(int i=n-1;i>=0;i--) {       result[i] = n-i-1;       for(int j=i;j<n;j++) {          if(isPalindrome(A.substr(i, j-i+1))) {             result[i] = min(result[i], 1 + result[j+1]);          }       }    }    return result[0]; } class Solution {    public:    int minCut(string s) {       return solve(s);    } }; main(){    Solution ob;    cout << (ob.minCut("ababba")); }

Input

“ababba”

Output

2