# Palindrome Partitioning with Changes

#### 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.
```

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]’

- Run a loop from j = i to ‘N’ - 1.
- 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]’

- Run a loop from j = i to ‘N’ - 1.
- 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

- Run a loop from i = 0 to i + len < ’N’
- 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.

- Run a loop from j = ’N’ - 1 to 0

- Run a loop from i = 0 to ’N’ - 1
- Return ‘dp[0][‘K’]’