HackerEarth Candies problem solution

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 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;
}

coding problems