Palindrome Partitioning
Vidhu
511

Given a string, a partitioning of the string is a palindrome partitioning if every substring of the partition is a palindrome. For example, “aba|b|bbabb|a|b|aba” is a palindrome partitioning of “ababbbabbababa”.

  • Determine the fewest cuts needed for a palindrome partitioning of a given string. For example, minimum of 3 cuts are needed for “ababbbabbababa”. The three cuts are “a|babbbab|b|ababa”. If a string is a palindrome, then minimum 0 cuts are needed. If a string of length n containing all different characters, then minimum n-1 cuts are needed.
  • This problem is a variation of [Matrix Chain Multiplication problem]
  • since we need to make partitions to try all combinations .If the string is a palindrome, then we simply return 0. Else, like the Matrix Chain Multiplication problem, we try making cuts at all possible places, recursively calculate the cost for each cut and return the minimum value.

Recursive Code

 bool isPallindrome(int i, int j, string str)
    {
       while(i < j)
    {
      if(str[i] != str[j])
        return false; 
      i++;
      j--;
    }
    return true;
    }
    int solve(int i, int j, string str)
    {
        if(i>=j)return 0;
        if(isPallindrome(i,j,str))return 0;
        
        int ans=INT_MAX;
        
        for(int k=i;k<=j-1;k++)
        {
            int tempAns = solve(i,k,str)+solve(k+1,j,str)+1;
            ans=min(ans,tempAns);
        }
        return ans;
    }
    int palindromicPartition(string str)
    {
        int n=str.length();
        return solve(0,n-1,str);
    }

Memoization

Note : Memoization will give TLE in most of the platforms since there is a more optimized approach

 int dp[501][501];
    bool isPallindrome(int i, int j, string str)
    {
       while(i < j)
    {
      if(str[i] != str[j])
        return false; 
      i++;
      j--;
    }
    return true;
    }
    int solve(int i, int j, string str)
    {
        if(i>=j)return 0;
        if(isPallindrome(i,j,str))return 0;
        
        if(dp[i][j]!=-1)
        return dp[i][j];
        
        int ans=INT_MAX;
        
        for(int k=i;k<=j-1;k++)
        {
            int tempAns = solve(i,k,str)+solve(k+1,j,str)+1;
            ans=min(ans,tempAns);
        }
        return dp[i][j]=ans;
    }
    int palindromicPartition(string str)
    {
        int n=str.length();
        memset(dp,-1,sizeof(dp));
        return solve(0,n-1,str);
    }

Memoization With Optimization (works on interview bit only)

  • In the above approach , we checked if(dp[i][j]==-1)
  • If not -1 then we simply returned the value dp[i][j] else we recur for the left part solve(str,i,k) and then for the right part solve(str,k+1,j)
  • But what if dp[i][j] is -1 but dp[i][k] was not -1 OR dp[i][j] is -1 but dp[k+1][j] was not -1
  • We didnt check these conditions and straightaway called for the left and the rigth part without checking if any of the parts were already calculated
  • This was the reason we were getting TLE on most of the platforms
  • So we'll take 2 variables left & right and if dp[i][k] is not -1 then we'll put value of dp[i][k] in left else we'll call for the solve(i,k,str) for the left part and put ints value into left
  • Similarly we'll do this for right variable and at last return 1 + left + right
  int dp[501][501];
    bool isPallindrome(int i, int j, string str)
    {
       while(i < j)
    {
      if(str[i] != str[j])
        return false; 
      i++;
      j--;
    }
    return true;
    }
    int solve(int i, int j, string str)
    {
        if(i>=j)return 0;
        if(isPallindrome(i,j,str))return 0;
        
        if(dp[i][j]!=-1)
        return dp[i][j];
        
        int ans=INT_MAX;
        
        for(int k=i;k<=j-1;k++)
      { 
        int left,right;
        
        if(dp[i][k]!=-1)
        left=dp[i][k];
        
        else left=solve(i,k,str);
        
        dp[i][k]=left;
        
        if(dp[k+1][j]!=-1)
        right=dp[k+1][j];
        
        else right=solve(k+1,j,str);
        
        dp[k+1][j]=right;
        
        int tempAns = left + right +1;
        ans=min(ans,tempAns);
        
        }
        return dp[i][j]=ans;
    }
    int palindromicPartition(string str)
    {
        int n=str.length();
        memset(dp,-1,sizeof(dp));
        return solve(0,n-1,str);
    }
  • More optimized (works on leetcode by doing a minor change and passing strings by reference)
  • We can perform another optimization.
  • Currently, we are selecting the k i.e. the position where we want to partition the string from i to j, and then we call the recursive function on both partitions.
  • Instead of doing this, we can check first if the string from the i to k is palindrome or not and run the recursive call on the remaining right subproblem (k+1 to j) only if the string from i to k was a palindrome.
  • Because as per the question all the partitions must be a valid palindrome, so if our first part is not a palindrome, why to waste time recursing the remaining string (k+1 to j). So, we are making partition only if the string before the partition is a palindrome, and recursively doing this for the remaining string.
int dp[2000][2000];
    bool isPallindrome(string &str,int i, int j)
    {
       while(i < j)
    {
      if(str[i] != str[j])
        return false; 
      i++;
      j--;
    }
    return true;
    }
    int solve(int i, int j, string &str)
    {
        if(i>=j)return 0;
        
        if(dp[i][j]!=-1)
        return dp[i][j];
        
         if(isPallindrome(str, i, j)){
         dp[i][j]=0;
         return 0;
    }
        
        int ans=INT_MAX;
        
        for(int k=i;k<=j-1;k++)
      { 
         /*An Optimization: We will make the partition only if the string till the partition 
		(till Kth position) is a valid palindrome. Because the question states that all 
		partition must be a valid palindrome. If we dont check this, we will have to 
		perform recursion on the left subproblem too (solve(str, i, k)) and	we will waste 
		a lot of time on subproblems that is not required. Without this the code will give
		correct answer but TLE on big test cases. */
            
            if(isPallindrome(str, i, k)){
            int tempAns = 1+solve(k+1, j, str);
            ans = min(ans, tempAns);                
            } 
        }
        return dp[i][j]=ans;
    }
    int minCut(string str) {
        
        int n=str.length();
        memset(dp,-1,sizeof(dp));
        return solve(0,n-1,str);
    }
Comments (1)