HackerEarth- Xsquare And Chocolates Bars (Dynamic Problem Solution)

XSquare And Chocolate Bars (HackerEarth)

Dynamic Programming, Easy

Solution:-

#include<bits/stdc++.h>

using namespace std;

#define MAX_LEN 1000010

int arr[MAX_LEN];

string B;

char temp;

void init(int len)

{

    for(int i=0;i<=len;i++)

        arr[i]=0;

}

int cal_max(string B,int len)

{

    init(len);

    if(len<3)

        return len;

    int g_max=0;

    bool flag=B[0]==B[1];

    for(int i=2;i<len;i++)

    {

        if(!(B[i]==B[i-1] && flag))

            arr[i]=3+(i-3>=0?arr[i-3]:0);

        flag=B[i]==B[i-1];

        if(g_max<arr[i])

            g_max=arr[i];

    }

    return len-g_max;

}

int main()

{

    int tc,i,len,ans,j;

    cin>>tc;

    while(tc--)

    {

        cin>>B;

        len=B.length();

        cout<<cal_max(B,len)<<endl;

    }

    return 0;

}