0w1

HR Bear and Steady Gene ( Binary Search )

https://www.hackerrank.com/challenges/bear-and-steady-gene
I knew it can be solved with crawling, but writing binary search was easier, and worked fine as well.
Try removing ( int ) before s.size() in the function ok(), and call ok() with parameter len = 0. You might find it surprising as I did, that it will show -1 > some positive value. This happens because it is integer compared against size_t ( which is unsigned ), and -1 will be converted into MAX_UNSIGNED_INT - 1 before comparison ( which I though size_t was the one that will be casted ). Anyways, I'll try to avoid implicit casting from now on. Here is a site that might be useful reading about.
c++ - Why does this if condition fail for comparison of negative and positive integers - Stack Overflow

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

typedef long long ll;
typedef pair< int, int > pii;
typedef vector< int > vi;
typedef vector< vi > vvi;
typedef vector< pii > vpii;
typedef vector< char > vch;

const int INF = 0x3f3f3f3f;

// #define MULTIPLE_CASES

bool ok( int len, const string &s, const vvi &pcnt, const vch &gen ){
    // cout << len - 1 << ( len - 1 < ( int )s.size() ? "<" : ">" ) << s.size() << endl;
    for( int i = 0; i + len - 1 < ( int )s.size(); ++i ){
        bool fail = false;
        for( int j = 0; j < 4; ++j ){
            int cnt = pcnt[ gen[ j ] ][ i + len ] - pcnt[ gen[ j ] ][ i ];
            int remain = pcnt[ gen[ j ] ][ s.size() ] - cnt;
            if( remain > s.size() / 4 ) fail = true;
        }
        if( !fail ) return true;
    }
    return false;
}

void solve(){
    int N; cin >> N;
    string s; cin >> s;

    const vch gen = { 'A', 'C', 'T', 'G' };

    vvi pcnt( 256, vi( N + 1 ) ); // 1 idx
    for( int i = 0; i < s.size(); ++i )
        for( int j = 0; j < 4; ++j )
            pcnt[ gen[ j ] ][ i + 1 ] = pcnt[ gen[ j ] ][ i ] + ( s[ i ] == gen[ j ] );

    int lb = 0, rb = N;
    int ans = -1;
    while( lb <= rb ){
        int mid = lb + rb >> 1;
        if( ok( mid, s, pcnt, gen ) ) ans = mid, rb = mid - 1;
        else lb = mid + 1;
    }

    cout << ans << "\n";
}

int main(){
    ios::sync_with_stdio( false );
    cin.tie( 0 );
    cout.tie( 0 );

    #ifdef MULTIPLE_CASES
        int T; cin >> T; while( T-- ) solve();
    #endif

    #ifndef MULTIPLE_CASES
        solve();
    #endif

    return 0;
}