Palindrome Partitioning III

Moderate
0/80
Average time to solve is 20m
4 upvotes
Asked in companies
AdobeUber

Problem statement

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?

Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
6 2
coding
6 6
ninjas
Sample Output 1:
2
0
Explanation For Sample Input 1:
Test Case 1 :  
The string given by Alice is “coding” and ‘K’ = 2
One possible way is to change ‘d’ to ‘c’ and ‘g’ to ‘i’, the resulting string will be “cocini”

Now we can divide the new string into 2 substrings “coc” and “ini”
So the minimum required change is 2.

Test Case 2 : 
The string given by Alice is “ninjas” and ‘K’ = 6

We can divide the string into 6 substrings of length 1.
So the minimum required change is 0.
Sample Input 2:
1
6 3
aabbcc
Sample Output 2:
0
Hint

Can you check all possible partitions to divide the given string into exactly ‘K’ non-empty disjoint substrings?

Approaches (3)
Brute force

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’.
Time Complexity

O(N * (2 ^ (N - 1) ) ), where ‘N’ is the length of the given string

 

There are (N * (N - 1) ) / 2 different substrings and it takes O(N) time to compute changes for each substring. Therefore it's O(N ^ 3) asymptotically.

 

In the worst case, ‘K’ can be up to ‘N’. Therefore there are 2 ^  (N - 1) possible ways to partition the given string (refer to this link for proof) and for each partitioning, it takes O(N)

 

So, the total time complexity will be O(N * 2 ^ (N - 1)) + O(N ^ 3) i.e O(N  * 2 ^  (N - 1))

Space Complexity

O(N ^ 2), where ‘N’ is the length of the given string. 

 

It takes O(N ^ 2) space to store the changes for each substring.

 

Our ‘allPartitions’ function requires O(K) space in the form of recursive stack space, where ‘K’ is an integer given in the problem

 

So, the total space complexity will be O(N ^ 2)  + O(K)

Code Solution
(100% EXP penalty)
Palindrome Partitioning III
Full screen
Console