Hackerearth | Candy problem | Help

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.

  1. 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.
  2. 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
1 Like

Can you please elaborate more? Or you could write down pseudo code to clarify more. What is ‘mi’ at here?

https://ideone.com/uhSNlG - My code, Out of 26 test cases, it gives AC in 20, and TLE in rest.

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.

Thanks

1 Like

mi is length of current string considered. i.e. mi=(low+high)/2
see https://ideone.com/1ZS3no for further implementation