Palindrome Partitioning III

The idea here is to check all possible partitions such that it divides the given string into exactly ‘K’ non-empty disjoint substrings. We will try to divide the given string into ‘K’ non-empty disjoint substrings. We will calculate the minimum number of changes required to make it a palindrome for each substring and then we will take the sum of all ‘K’ substrings to get the minimum number of required changes for the whole string. Recursively we will try all possible divisions and compute their corresponding minimum number of changes. Finally, we will take a minimum of all such divisions.

Algorithm:

• Declare a 2 - D array of integers, say ‘changes[N][N]’
• For every substring of the given string, precompute the minimum number of characters that you need to change to make that substring a palindrome.
• Run a loop from i = 0 to ‘N’ - 1. Here ‘N’ is the length of the string.
  • Run a loop from j = i  to ‘N’ - 1.
    • Call ‘numChanges’ function to get the minimum number of changes to make substring ‘S[i. . .j]’ a palindrome
    • Store this in ‘changes[i][j]’
• Call ‘allPartitions’ function and store its returned value into a variable, say ‘answer’
• Return ‘answer’

Description of ‘numChanges’ function

This function will take three parameters:

• str: A string given in the problem.
• low: An integer denoting the starting index of the substring
• high: An integer denoting the ending index of the substring

int numChanges(str, low, high):

• Declare a variable ‘answer’ to store the minimum number of changes required to make ‘str’ palindrome and initialize it with 0
• Run a loop while ‘low’ < ’high’
  • If ‘str[low]’ != ‘str[high]’ then increment the ‘answer’ since we have to change either str[low] or str[high] to make the substring Palindrome
  • Increment ‘low’ and decrement ‘high’ by one i.e. do ‘low’ := ’low’ +  1 and ‘high’ := ’high’ - 1
• Return ‘answer’.

Description of ‘allPartitions’ function

This function will take three parameters :

• low: An integer denoting the starting index of the current substring
• high: An integer denoting the ending index of the current substring
• k: An integer denoting the number of divisions of current substring

int allPartitions(low, high,k):

• If ‘k’ == 1 then return ‘changes[low][high]’
• Declare a variable to keep track of the optimal division, say ‘answer’
• Do ‘answer’ := ’changes[low][low]’ + allPartitions(low + 1 , high, k - 1)
• Run a loop from low + 1 to high - k + 1
  • ‘answer’ = min(‘answer’, ’changes[low][i]’ + allPartitions(i + 1, high, k - 1))
• Return ‘answer’.

The idea here is to optimize the previous approach using dynamic programming. We are calling some functions again and again so we will call them once and store their values in a ‘dp’ array.

The below diagram shows that allPartitions(3, 4, 1) is called multiple times, hence there are overlapping subproblems

Algorithm:

• Declare a ‘dp’ array to store overlapping subproblems and initialize it with -1
• Declare a 2 - D array of integers, say ‘changes[N][N]’
• For every substring of the given string, precompute the minimum number of characters that you need to change to make that substring a palindrome.
• Run a loop from i = 0 to ‘N’ - 1. Here ‘N’ is the length of the string.
  • Run a loop from j = i  to ‘N’ - 1.
    • Call ‘numChanges’ function to get the minimum number of changes to make substring ‘S[i. . .j]’ a palindrome
    • Store this in ‘changes[i][j]’
• Call ‘allPartitions’ function and store its returned value into a variable, say ‘answer’
• In the ‘allPartitions’ function store the answer for each subproblem in the ‘dp’ array and reuse it if required.
• Return ‘answer’

Description of ‘numChanges’ function

This function will take three parameters :

• str: A string given in the problem.
• low: An integer denoting the starting index of the substring
• high: An integer denoting the ending index of the substring

int numChanges(str, low, high):

• Declare a variable ‘answer’ to store the minimum number of changes required to make ‘str’ palindrome and initialize it with 0
• Run a loop while ‘low’ < ’high’
  • If ‘str[low]’ != ‘str[high]’ then increment the ‘answer’ since we have to change either str[low] or str[high] to make the substring Palindrome
  • Increment ‘low’ and decrement ‘high’ by one i.e. do ‘low’ := ’low’ +  1 and ‘high’ := ’high’ - 1
• Return ‘answer’.

Description of ‘allPartitions’ function

This function will take three parameters :

• low: An integer denoting the starting index of the current substring
• high: An integer denoting the ending index of the current substring
• k: An integer denoting the number of divisions of current substring

int allPartitions(low, high, k):

• If ‘k’ == 1 then return ‘changes[low][high]’
• If ‘dp[low][k]’ != -1 return ‘dp[low][k]’ i.e if the answer to this subproblem is already calculated then we’ll just reuse the computed answer.
• Declare a variable to keep track of the optimal division, say ‘answer’
• ‘answer’: = ’changes[low][low]’ + allPartitions(low + 1, high, k - 1)
• Run a loop from low + 1 to high - k + 1
  • ‘answer’ = min(‘answer’, ’changes[low][i]’ + allPartitions(i + 1, high, k - 1))
• ‘dp[low][k]’ : = ’answer’ store the computed answer in the dp table
• Return ‘answer’

The idea here is to use iterative dynamic programming. We will calculate answers from bottom to top. We will create 2 2 - D arrays ‘changes[N][N]’ and ‘dp[N][K]’. ‘Changes[i][j]’ will store the minimum number of characters that we need to change to make substring ‘S[ i. . .j]’ a palindrome and ‘dp[i][k]’ will store the minimum number of characters that we need to change to divide the substring ‘S[i. . .N]’ into ‘K’ non-empty disjoint palindromic substrings.

Algorithm:

• Declare a 2-D integer array ‘changes[N][N]’ to store the minimum number of characters that we need to change for each substring of the given string
• Run a loop from i = 0 to ‘N’ - 1, here ‘N’ is the length of the string
  • Make ‘changes[i][i]’ := 0 since all strings of length 1 are a palindrome.
• Run a loop from i = 1 to ‘N’ - 1
  • If ‘S[i]’ == ’S[i - 1]’ make ‘changes[i - 1][i]’ := 0 since substring ‘S[i - 1, i]’ is already a palindrome, we don’t have to do any changes.
  • else make ‘changes[i - 1][i]’ = 1, we can change either S[i - 1] or S[i] to make substring S[i - 1 , i] palindrome.
• Run a loop from len =  2 to len < ‘N’, here ‘N’ is the length of the string
  • Run a loop from i = 0 to i + len < ’N’
    • j := i + len
    • For a substring ‘S[i, j]’, if ‘S[i]’ is the same as ‘S[j]’ then the minimum number of characters that we need to change to make this substring a  palindrome is equivalent to the minimum number of character changes to make substring ‘S[i + 1, j - 1]’ palindrome.
    • If ‘S[i]’ == ‘S[j]’ then do ‘changes[i][j]’ := ‘changes[i+1][j-1]’
    • For a substring ‘S[i, j]’, if ‘S[i]’ is not the same as ‘S[j]’ then the minimum number of characters that we need to change to make this substring a  palindrome is equivalent to the minimum number of character changes to make substring ‘S[i + 1, j - 1]’ palindrome plus 1 since we can change either ‘S[i]’ or ‘S[j]’ to  make ‘S[i, j]’ palindrome
    • If ‘S[i]’ != ‘S[j]’ then do ‘changes[i][j]’ := ‘changes[i+1][j-1]’ + 1
• Declare a 2-D array ‘dp[N][K]’ and initialize it with ‘N’ + 1, here ‘N’ is the length of the string, and ‘dp[i][k]’ will store the minimum number of characters that we need to change to divide the substring ‘S[i. . .N]’ into ‘K’ non-empty disjoint palindromic substrings.
• Run a loop from i = 0 to ‘N’ - 1
  • Make ‘dp[i][1]’ = ’changes[i][N-1]’, since the minimum number of characters that we need to change to divide the substring ‘S[i, N]’ into exactly 1 part is the same as the minimum number of changes required to make substring ‘S[i, N]’ palindrome.
• Run a loop from k = 2 to k <= ‘K’
  • Run a loop from i = 0 to ’N’ - 1
    • Run a loop from j = ’N’ - 1 to 0
      • If i > (j - 1) break the loop
      • ‘dp[i][k]’ := min(‘dp[j][k - 1]’ + ’changes[i][j - 1]’, ’dp[i][k]’), here ‘dp[i][k]’ denotes the minimal number of characters required to change upon the substring ‘S[i, N]’, such that ‘S[i, N]’ can be divided into exactly ‘k’ non-empty disjoint substrings with each substring a palindrome.
• Return ‘dp[0][‘K’]’