SlidingWindow_BinarySearch_ProbSoln_Shanto

/*    BISMILLAHIR-RAHMANIR-RAHIM
 ____________________________________
|                                    |
|      SHANTO_SUST_SWE-19__029       |
|      shanto-swe029.github.io       |
|____________________________________|
*/

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

bool isCorrect( string s, int n, int** cumSum )
{
    int len = s.size();
    for( int i = n; i <= s.size(); i++ ) {
        int x = ( cumSum[0][i] - cumSum[0][i - n] ) * ( cumSum[1][i] - cumSum[1][i - n] ) * ( cumSum[2][i] - cumSum[2][i - n] );
        if ( x > 0 ) {
            return true;
        }
    }
    return false;
}

int BinarySearch_SlidingWindow( string s, int** cumSum )
{
    int n = s.size();
    int BEG = 1, END = n, MID;
    int length = n + 2;

    while( BEG <= END ) {
        MID = ( int ) ( BEG + END ) / 2;
        bool b = isCorrect( s, MID, cumSum );
        if( !b ) {
            BEG = MID + 1;
        }
        else {
            END = MID - 1;
            if( MID < length ) {
                length = MID;
            }
        }
    }

    return length;
}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif

    string s;
    std::cin >> s;
    int **cumSum;
    cumSum = (int **) malloc( sizeof(int *) * 3 );
    for( int i = 0; i < 3; i++ ) {
        cumSum[i] = (int *) malloc( sizeof(int *) * ( s.size() + 1 ) );
    }

    cumSum[0][0] = 0;
    cumSum[1][0] = 0;
    cumSum[2][0] = 0;
    int s1 = 0, s2 = 0, s3 = 0;
    for( int i = 0; i < s.size(); i++ ) {
        if( s[i] == '1' ) {
            s1++;
            cumSum[0][i+1] = s1;
            cumSum[1][i+1] = s2;
            cumSum[2][i+1] = s3;
        }
        else if( s[i] == '2' ) {
            s2++;
            cumSum[0][i+1] = s1;
            cumSum[1][i+1] = s2;
            cumSum[2][i+1] = s3;
        }
        else {
            s3++;
            cumSum[0][i+1] = s1;
            cumSum[1][i+1] = s2;
            cumSum[2][i+1] = s3;
        }
    }

    int ans = BinarySearch_SlidingWindow( s, cumSum );

    if( ans > s.size() ) std::cout << "0 ->> no substring found" << endl;
    else std::cout << "minimum legth of the substring : " << ans << endl;
}

//ALHAMDULILLAH