**Bear and Steady Gene

Bear and Steady Gene

A gene is represented as a string of length n$n$ (where n$n$ is divisible by 4$4$), composed of the letters A$\text{A}$, C$\text{C}$, T$\text{T}$, and G$\text{G}$. It is considered to be steady if each of the four letters occurs exactly n4$\frac{n}{4}$ times. For example, GACT$\text{GACT}$ and AAGTGCCT$\text{AAGTGCCT}$ are both steady genes.

Bear Limak is a famous biotechnology scientist who specializes in modifying bear DNA to make it steady. Right now, he is examining a gene represented as a string s$s$. It is not necessarily steady. Fortunately, Limak can choose one (maybe empty) substring of s$s$ and replace it with any substring of the same length.

Modifying a large substring of bear genes can be dangerous. Given a string s$s$, can you help Limak find the length of the smallest possible substring that he can replace to make s$s$ a steady gene?

Note: A substring of a string S$S$ is a subsequence made up of zero or more consecutivecharacters of S$S$.

Input Format

The first line contains an interger n$n$ divisible by 4$4$, denoting the length of a string s$s$.
The second line contains a string s$s$ of length n$n$. Each character is one of the four: A$\text{A}$, C$\text{C}$, T$\text{T}$, G$\text{G}$.

Constraints

• 4≤n≤500000$4\le n\le 500000$
• n$n$ is divisible by 4$4$

Subtask

• 4≤n≤2000$4\le n\le 2000$ in tests worth 30%$30\mathrm{\%}$ points.

Output Format

On a new line, print the minimum length of the substring replaced to make s$s$ stable.

Sample Input

8  
GAAATAAA

Sample Output

5

Explanation

One optimal solution is to replace a substring AAATA$\text{AAATA}$ with TTCCG$\text{TTCCG}$, resulting in GTTCCGAA$\text{GTTCCGAA}$. The replaced substring has length 5$5$, so we print 5$5$ on a new line.

-------------------------------------------EDITORIAL--------------------------------------

THIS PROBLEM CAN EASILY SOLVE IF WE USE DISCRET BINARY SEARCH , 

MAIN THING IS THAT WHICH SUBSTRING IS VALID TO REPLACE ..

IF A SUB STRING HAVE  EXTRA CHARACTERS WHICH ARE PRESENT IN THE STRING ( IT CAN HAVE SOME NON EXTRA CHARS ALSO ) THAT SUB STRING CAN BE REPLACE..

NOW SUPPOSE WE WANT TO REPLACE A SUB STRING WHICH END AT INDEX  i , 

THAN WE CAN REPLACE MAXIMUM FROM INDEX (0,i) AND MINIMUM AT SOME INDEX (j,i) , WE CAN FIX THIS INTERMEDIATE INDEX USING THE DISRCRET BINARY SEARCH ...

MAIN OBSERVATION IS THAT IF SUB STRING (j,i )  CAN BE A VALID SUBSTRING TO REPLACE  THAN A SUB STRING (k,i) WHERE k<j is also a valid sub string to replace  

-----------------------------------------code-------------------------------------------

#include<bits/stdc++.h>

using namespace std;

struct st

{

int g,a,t,c;

} stt[1000000];

int main()

 {

  int n;

   cin>>n;

   string s;

   cin>>s;

   int G=0,A=0,C=0,T=0;

    int len=s.length();

    stt[0].c=0;

    stt[0].a=0;

    stt[0].t=0;

    stt[0].g=0;

   //  cout<<s<<endl;

   

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

     {

      if(s[i-1]=='G') 

 {

  G++;

  stt[i].g=1;

 }

      else if(s[i-1]=='C') 

{

C++;

stt[i].c=1;

}

 

      else if(s[i-1]=='A')

{

A++;

stt[i].a=1;;

 } 

      else 

 {

  // cout<<" wtf"<<endl;

  T++;

  stt[i].t=1;

  //cout<<stt[i].t<<endl;

 }

 

 

  stt[i].a+=stt[i-1].a;

  stt[i].c+=stt[i-1].c;

  stt[i].g+=stt[i-1].g;

  stt[i].t+=stt[i-1].t;

  

     

}

  n=len;

int exa=A-n/4;

int exg=G-n/4;

int exc=C-n/4;

int ext=T-n/4;

         if(A==n/4 && T==n/4 && G==n/4 && C==n/4 )

          {

          cout<<0<<endl;

          return 0;

 }

int ans=1000000;

 

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

 {

 

   int l=1,r=i;

   int c=0;

     

   while(c<=70)

    {

   

     c++;

     int mid=(l+r)/2;

       if(  exa<=stt[i].a-stt[mid-1].a && exg<=stt[i].g-stt[mid-1].g && exc<=stt[i].c-stt[mid-1].c && ext<=stt[i].t-stt[mid-1].t  )

         {

            l=mid;

            ans=min(ans,i-mid+1);

  }

 

  else

  {

  r=mid;

  }

}

 }

   if(ans!=1000000)

  cout<<ans<<endl;

  else cout<<0<<endl;

 }