CodeChef (Purify It)

#include<bits/stdc++.h>

using namespace std;

int lcs(string s, string s1)

{

    int n = s.size();

    int m = s1.size();

    int L[n+1][m+1], i, j;

    for(i=0;i<=n;i++)

    {

        for(j=0;j<=m;j++)

        {

            if(i==0 || j == 0)

                L[i][j] = 0;

            else if(s[i-1] == s1[j-1])

                L[i][j] = 1 + L[i-1][j-1];

            else

                L[i][j] = max(L[i-1][j], L[i][j-1]);

        }

    }

    return L[n][m];

}

int main()

{

    int t, i;

    cin >> t;

    string s1 = "", s2 = "";

    for(i=0;i<1000;i++)

    {

        s1 += '1';

        s2 += '0';

    }

    for(i=0;i<1000;i++)

    {

        s1 += '0';

        s2 += '1';

    }

    for(i=0;i<1000;i++)

    {

        s1 += '1';

        s2 += '0';

    }

    cout << s1 << "\n";

    cout << s2 << "\n";

    while(t--)

    {

        string s;

        cin >> s;

        int n = s.size();

        cout << n - max(lcs(s, s1), lcs(s, s2)) << "\n";

    }

    return 0;

}