Palindrome Partitioning III in C++

Suppose we have a string s that is containing lowercase letters and an integer k. We have to maintain some properties. These are −

• First, we have to change some characters (if needed) of s to other lowercase English letters.
• Then divide the string s into k substrings such that each substring is a palindrome.

We have to find the minimal number of characters that we need to change to divide the string.

So if the string is like “ababbc” and k = 2, then the answer will be 1, as we have to change one character to split this into two palindrome strings. So if we change c to b, or second last b to c, then we can get one palindrome like either “bbb” or “cbc”, and another palindrome is “aba”.

To solve this, we will follow these steps −

• Define an array memo of size: 105 x 105.
• Define a function solve(), this will take s, idx, k, one 2D array > dp,
• if idx is same as size of s, then −
  • return when k is 0 then 0 otherwise 1000
• if memo[idx][k] is not equal to -1, then −
  • return memo[idx][k]
• if k <= 0, then −
  • return inf
• ans := inf
• for initialize i := idx, when i < size of s, update (increase i by 1), do −
  • ans := minimum of ans and dp[idx][i] + call the function solve(s, i + 1, k - 1, dp)
• return memo[idx][k] = ans
• From the main method, do the following
• n := size of s
• fill memo with -1
• Define one 2D array dp of size n x n
• for initialize l := 2, when l <= n, update (increase l by 1), do −
  • for initialize i := 0, j := l - 1, when j < n, update (increase j by 1), (increase i by 1), do −
    • if l is same as 2, then −
    • dp[i][j] := true when s[i] is not same as s[j]
    • Otherwise
      • dp[i][j] := dp[i + 1][j - 1] + 0 when s[i] is same as s[j]
• return solve(s, 0, k, dp)

Let us see the following implementation to get better understanding −

Example

 Live Demo

#include <bits/stdc++.h> using namespace std; typedef long long int lli; class Solution { public:    int memo[105][105];    lli solve(string s, int idx, int k, vector < vector <int> > &dp){       if(idx == s.size()) {          return k == 0? 0 : 1000;       }       if(memo[idx][k] != -1) return memo[idx][k];       if(k <= 0)return INT_MAX;       lli ans = INT_MAX;       for(int i = idx; i < s.size(); i++){          ans = min(ans, dp[idx][i] + solve(s, i + 1, k - 1, dp));       }       return memo[idx][k] = ans;    }    int palindromePartition(string s, int k) {       int n = s.size();       memset(memo, -1, sizeof(memo));       vector < vector <int> > dp(n, vector <int>(n));       for(int l =2; l <= n; l++){          for(int i = 0, j = l - 1; j <n; j++, i++){             if(l==2){                dp[i][j] = !(s[i] == s[j]);             }else{                dp[i][j] = dp[i+1][j-1] + !(s[i] == s[j]);             }          }       }       return solve(s, 0, k, dp);    } }; main(){    Solution ob;    cout << (ob.palindromePartition("ababbc", 2)); }

Input

“ababbc”

Output

1