I got stuck in this questions, please suggest me any elegant approach to solve this problem.
You are given a string S consisting of lowercase English letters denoting different types of candies. A substring of a string S is a string S’ that occurs in S. For example, “bam” is a substring of “babammm”. Each candy costs 1 unit. You can pick some continuous candies such that you can create a palindrome of length K by using some or all picked candies and rearranging them. Your task is to find the minimum cost to create a palindrome of length K.
Input Format:
First line contains string S.
Next line contains an integer T denoting the number of test cases.
Next T lines contain a single integer K.
Output Format:
For each test case, print minimum cost as mentioned above. If you cannot create a palindrome of length K then, simply print -1.
Constraints
1 <= |S| <= 10^5
1 <= T <=10
1<=K<=10^5
Sample Input
babammm
2
2
5
Sample Output
2
5
Explanation
Test Case 1: You can pick candies denoted by “mm” and create a palindrome of size 2. So the cost will be 2 units.
Test Case 2: You can pick candies denoted by “babam” and rearrange them, “bamab”, to create a palindrome of size 5. So the cost will be 5 units.
Here you can use binary search+prefix sum. First store the prefix count of a-z in array dp[N][26]. Now just start binary search to find minimum length string from low=k to high=string.size().Now consider mid=(lo+hi)/2.
Now for all substrings of length mi just check the count of characters from a-z occurring odd number of times.
if k is even just calculate cur_len=mi-count_of_odd_chars. If cur_len>=k then just store it as ans and set
low=mi+1. Else check for remaining substrings of length mi.
if k is odd ,
2.1 if count_of_odd_chars=0 skip this string
2.2 else find cur_len=mi-count_of_odd_chars+1 to include one extra odd character. Now just check for cur_len>=k
if it holds change low=mid+1 else skip the string
Logic - Store for every ith index the number of a, b, c … z till that index. freq[i][26]
Represented by freq[][] array in code.
For every query do a binary search with low = k, and high = s.length in the beginning.
Find mid. Check if we can generate palindrome from length = k, with “mid” characters. Done by checking all window of length mid from i = 0 to length - mid.
In a particular window of length mid = [i, i + mid). We find frequency of characters (a…z) from i to i + mid, could be calculated using freq[][] array.
Answer (for this window) = Count number of even frequency character using freq[][] array. for odd frequency sort them in increasing order. Add to Answer, odd frequency - 1 excluding the last odd frequency. Add to answer the last odd frequency.
Basically in above step we are making a palindrome with maximum characters, we can take all even frequency character and split them in left
and right half. For all odd frequency except the maximum one we take (odd - 1) for every such characters (make them even), in the end we take the maximum odd frequency character count (keeping it in centre).
if Answer >= n, we found the palindrome with mid characters. so we do high = mid - 1
else low = mid + 1.