Bear and Steady Gene

                            Solution in C :

In   C++ :








#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	string s;
	cin>>n>>s;
	int a=0;
	int c=0;
	int t=0;
	int g=0;
	for (int i=0;i<n;i++){
		if (s[i]=='A') a++;
		if (s[i]=='C') c++;
		if (s[i]=='T') t++;
		if (s[i]=='G') g++;
	}
	a-=n/4;
	c-=n/4;
	t-=n/4;
	g-=n/4;
	int i2=0;
	int ca=0;
	int cc=0;
	int ct=0;
	int cg=0;
	int v=n;
	for (int i=0;i<n;i++){
		while (i2<n&&(ca<a||cc<c||ct<t||cg<g)){
			if (s[i2]=='A') ca++;
			if (s[i2]=='C') cc++;
			if (s[i2]=='T') ct++;
			if (s[i2]=='G') cg++;
			i2++;
		}
		if (!(ca<a||cc<c||ct<t||cg<g)){
			v=min(v, i2-i);
		}
		if (s[i]=='A') ca--;
		if (s[i]=='C') cc--;
		if (s[i]=='T') ct--;
		if (s[i]=='G') cg--;
	}
	cout<<v<<endl;
}










In    Java  :







import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    
    public static int code(char c) {
        if (c == 'A') return 0;
        if (c == 'C') return 1;
        if (c == 'G') return 2;
        return 3;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine();
        String str = in.nextLine();
        int j = n-1;
        int[] count = new int[4];
        while (true) {
            if (j == -1) {
                System.out.println("0");
                return;
            }
            if (count[code(str.charAt(j))] + 1 > n/4) {
                j++;
                break;
            }
            count[code(str.charAt(j))]++;
            j--;
        }
        int result = j;
        for (int i = 0; i < n; i++) {
            count[code(str.charAt(i))]++;
            while(count[code(str.charAt(i))] > n/4) {
                if (j == n) {
                    System.out.println(result);
                    return;
                }
                count[code(str.charAt(j))]--;
                j++;
            }
            result = Math.min(result, j - i - 1);
        }
        System.out.println(result);
    }
}










In   C  :







#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>

#define MAX_L 500002

static int cvt(int c)
{
	switch (c) {
	case 'A':
		return 0;
	case 'T':
		return 1;
	case 'C':
		return 2;
	case 'G':
		return 3;
	}
	abort();
}

static bool check(int cnts[][MAX_L + 1], int n, int i, int l)
{
	bool ok = 1;
	int sum = 0;
	for (int j = 0; j < 4; j++) {
		int diff = n/4 - (cnts[j][n] - (cnts[j][i + l] - cnts[j][i]));
		ok &= diff >= 0;
		sum += diff;
	}
	return ok && sum == l;
}

static int subst(char s[MAX_L], int n)
{
	int res = INT_MAX;
	static int cnts[4][MAX_L + 1];
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 4; j++) {
			cnts[j][i] = cnts[j][i-1];
		}
		cnts[s[i-1]][i] += 1;
	}

	for (int i = 0; i < n; i++) {
		int len = 1;
		int l, r;
		while (i + len <= n) {
			if (check(cnts, n, i, len))
				break;
			len *= 2;
		}
		if (i + len > n) {
			len = n - i;
			if (!check(cnts, n, i, len))
				continue;
		}
		l = len / 2;
		r = len;
		while (l < r) {
			int m = l + (r - l)/2;
			if (check(cnts, n, i, m)) {
				r = m;
				len = r;
			} else {
				l = m + 1;
			}
		}
		if (len < res)
			res = len;
	}
	return res;
}

int main()
{
	int n;
	static char s[MAX_L];
	fgets(s, MAX_L, stdin);
	sscanf(s, "%d", &n);
	fgets(s, MAX_L, stdin);
	for (int i = 0; i < n; i++) {
		s[i] = cvt(s[i]);
	}
	printf("%d", subst(s, n));
	return 0;
}









In   Python3  :







from collections import Counter

n = int(input())
m = n // 4
s = input()
cnt = {'G': 0, 'A': 0, 'C': 0, 'T': 0}
cnt.update(Counter(s))

if all(map(lambda x: x == m, cnt.values())):
    print(0)
    exit()
low, high = 0, n
while high - low > 1:
    mid = (high + low) // 2
    cnt_tmp = dict(cnt)
    for i in range(mid):
        cnt_tmp[s[i]] -= 1
    if all(map(lambda x: x <= m, cnt_tmp.values())):
        high = mid
        continue
    for i in range(mid, n):
        cnt_tmp[s[i - mid]] += 1
        cnt_tmp[s[i]] -= 1
        if all(map(lambda x: x <= m, cnt_tmp.values())):
            high = mid
            break
    else:
        low = mid
print(high)