In this HackerEarth Candies problem solution, 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. Your task is to find the minimum cost to create a palindrome of length K.


HackerEarth Candies problem solution


HackerEarth Candie's problem solution.

#include <bits/stdc++.h>
using namespace std;

bool check(int arr[],int k)
{
int flag=0;
int val=0;
for(int i=0;i<26;i++)
{
if(arr[i]==0)
{
continue;
}
else if(arr[i]==1)
{
flag=1;
}
else
{
if(arr[i]&1)
flag=1;
val+=arr[i]/2;
}
}
if(k&1)
{
if(2*val+flag>=k)
return true;
}
else
{
if(2*val>=k)
return true;
}
return false;
}
bool fun(string s, int x, int k)
{
int fre[26]={0};
for(int i=0;i<x;i++)
{
fre[s[i]-'a']++;
}
if(check(fre,k))
return true;
for(int i=x;i<s.length();i++)
{
fre[s[i-x]-'a']--;
fre[s[i]-'a']++;
if(check(fre,k))
return true;
}
return false;
}
int main()
{
string s;
cin>>s;
int t;
cin>>t;
while(t--)
{
int k;
cin>>k;
int lo,mid,hi;
int ans=-1;
lo=k;
hi=s.length();
while(hi-lo>=0)
{
mid = (lo+hi)/2;
if(fun(s,mid,k))
{
ans=mid;
hi=mid-1;
}
else
{
lo=mid+1;
}
}
cout<<ans<<"\n";
}
return 0;
}

Second solution

#include <bits/stdc++.h>

#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define be begin()
#define en end()
#define le length()
#define sz size()
#define all(x) (x).begin(),(x).end()
#define alli(a, n, k) (a+k),(a+n+k)
#define REP(i, a, b, k) for(__typeof(a) i = a;i < b;i += k)
#define REPI(i, a, b, k) for(__typeof(a) i = a;i > b;i -= k)
#define REPITER(it, a) for(__typeof(a.begin()) it = a.begin();it != a.end(); ++it)

#define y0 sdkfaslhagaklsldk
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd
#define have adsgagshdshfhds

#define eps 1e-6
#define pi 3.141592653589793

using namespace std;

template<class T> inline T gcd(T a, T b) { while(b) b ^= a ^= b ^= a %= b; return a; }
template<class T> inline T mod(T x) { if(x < 0) return -x; else return x; }

typedef vector<int> VII;
typedef vector<ll> VLL;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef pair<int, PII > PPII;
typedef vector< PII > VPII;
typedef vector< PPII > VPPI;

const int MOD = 1e9 + 7;
const int INF = 1e9;

// Template End

int A[30];

int check(bool odd) {
int x;
if (odd) {
x = 0;
bool flag = false;
REP(i, 0, 26, 1) {
if (A[i] & 1) x += A[i] - 1, flag = true;
else x += A[i];
}
if (flag) x++;
else x--;
}
else {
x = 0;
REP(i, 0, 26, 1) {
if (A[i] & 1) x += A[i] - 1;
else x += A[i];
}
}
return max(0, x);
}

int main(int argc, char* argv[]) {
if(argc == 2 or argc == 3) freopen(argv[1], "r", stdin);
if(argc == 3) freopen(argv[2], "w", stdout);
ios::sync_with_stdio(false);
string s;
int t, k, ans, p;
assert(cin >> s);
assert(1 <= s.le and s.le <= 100000);
assert(cin >> t);
assert(1 <= t and t <= 10);
while (t--) {
REP(i, 0, 30, 1) A[i] = 0;
assert(cin >> k);
assert(1 <= k and k <= 100000);
p = 0;
ans = INF;
REP(i, 0, s.le, 1) {
while (p < s.le and check(k & 1) < k) {
A[s[p] - 'a']++;
p++;
}
if (check(k & 1) >= k) ans = min(ans, p - i);
A[s[i] - 'a']--;
}
if (ans == INF) ans = -1;
cout << ans << endl;
}
return 0;
}