Palindrome Partitioning with Changes

Posted: 17 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

On Valentine’s Day, Alice and Bob planned to go on a dinner date, but Alice is still unsure about Bob, so she decided to give him a task. She gave him a string ‘S’ of length ‘N’ containing only lowercase English letters and an integer ‘K’ and told him that he could:

Change some characters of ‘S’ to other lowercase letters  (if required).

Divide ‘S’ into ‘K’ non-empty disjoint substrings such that each substring is a palindrome.

She asked Bob to find the minimum number of characters he needs to change to divide the given string in the required condition. Since Bob is busy preparing a perfect date for her, he called you to solve Alice’s challenge. Can you help Bob to impress her?

Input Format
The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains two space-separated integers, ‘N’ and ‘K’. Here ‘N’ denotes the length of the string, and ‘K’ is an integer given by Alice.

The next line contains a string ‘S’ of length ‘N’. Here ‘S’ is the string given by Alice to Bob. 
Output Format:
For each test case, print a single line containing a single integer denoting the minimum number of characters that Bob needs to change to divide ‘S’ into ‘K’ non-empty disjoint palindromic substrings.

The output of each test case will be printed in a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
1 <= N <= 50
1 <= K <= N
‘S’ contains only lowercase English letters.

Time limit: 1 sec.
Approach 1

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’.
Try Problem