using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        int result = steadyGene("ACAAAAATAAACAAAAACAAAAAAAAAATAAATACAATAAAAAAAAAAAATGAAATACAACAACAAATAAAATAAAAACGACTAAAAAATAAAAAAAAAAAAAAAAAGAGTACTAAAAAAAAAAAAAAAAAATAAAAAAAAAAAAAACACAATCAAAATAAACAAAAAAAAAAAAACCAAAATAATCAACAAAAAAAAAAAAAACAAAAACAACAACAAACAAAAAAAAACACAAACAAAAAAAAAAAAAAAACAAAACAAACAAAAAAAAAAAAACAAAAAAACAAAAAAAAAAAAAAAAACAAAAAAAAAAATAAAAAAAAAAAAAAAAAAAAAACAAACAAAAAAAAAAAATACAAAAAGCTATAAAAAAAAAAAAATTAAAAAACAAAAAAAAATAAAAAAAAAAAAAAAAAAAAAAAATAAAAAAAAAAAAAAAAAAAAAATAAAAAAAAAAAAAAAAAAGAAAAACAAAAAAAAAAAAAAAAACAACCAAAAAACAAAAAAAAACTAAAAAAAAAAAAAAAAAAAAAAAAAAATAACAAAAAACACAAAAAAAAAAAAGAAAGAAAAAAAACACAAAAAAAAACAAACAAAAAAAAAAAAAAAAAAAGAAAACAAAAAAACAAAAAAAACAAAAAAAAAACAAAAATTGGACAAAAAAAAACAAAAAAAAAAAACAAAAAAAGTAAAACAAATAAAAAAACAAAAAAAACAAAAAAAAAAAAAAAAAACAAAAAAGAAACAAAAAACAAAAAAAAATAACAAAACCAAAAAACAAATAAAAAACAAAAAAAATAACACAAAAAAAAAAAGAAACAAAAAAAAAAAAAAAAAAAAAAATTATAAAAAAAAAAAAAAAACAAAAAAAAAAAAAACAAAAAAAAAAGGAAAAAAAAAAAAAAAAAAAAAAAAAAATAACTAAACAAAAAAAAACAAACAAAAAATCAAAAAAAAAAAAGAAAAAAGAATAAGCAACAAAAACACAAAAAAAAAAAAAAAAAAAAAAAACATAAACAATAATAAAAAAAAAACAAAAAAAACAAAAGAACAACAAAAAACAAAACTAAACAAATAAAAAAAAAAAAACAAAAACTACAAAAAAAAAAAGAAAAAAAAAGAAAAAAAAACAAATAAAAGAAAAAAAAAAAAAAAAAAAACACAAAAAAAAAAATAAAAAAAAAAAAAAAAACAAAATAAACAAAAACAAAGAAAAAAACAAACAAAAAAAAAAAACAAAAAACTAAAAACAAAAAAAAAACAAAACACAAAAAAAAAAAAAAATAAAAAAAAAACAAAAAAACAAAAAGGAAAAAAAAAAAAGAACAAAAAAAAAAACAACAGAAAAAAGAAAAGAAAAAAAAAAAAAGACCACAAAATAAAAAAAAACAACAAACAAAAAAAAACAAAACAAAAAAACGAACAAAAAAAACAAAAACAAAAAAAAAAAAAAAAAAAAAAAGGCAAAAACAAAAAAAACAAAACAAAACAAAAAAACAAAAAAAAATTAAGATAAAGAACAAAAAAAGAAGAGAAAAAATTAACAAAAAAAAAAAAATAAAAAATACAAAAAGAAATAAAAAATACAACACACAACAAAAACGAAAAAAAAAAAAAAAACACAAAATAGAAAAAAAAAAAAAACAAAAAAAAAAAAAAGAAAAAAACAAAAAAAAAAAAATAAAAAAAAACGACACAGAAACAAAAAATAACAAAAAAAAAAAAAATAAAAAAAAAACAAAAAAAAAACAAAAAATAAAAAAAAAAACAAACAAAAAAAAAAAAAAAATAAAAAAAAAAAAAGCAAAACATAAACAAGAAAAAAAAAAAAAGTACAAATAACAAAACAAAAAAGACACTAAAAAAAAAAAAAAAAAACAAAAAAAAAAAAAAAAAAAAAAAAAGAAAAAAAACCACAAAACAAAAAAATAAAGCAAAAAAAAAAAAAAAAAAAAAAAAAAAATAAATGAAAAAAAAAAGAAAACCAAAAAAATAAAAGA");

        Console.WriteLine("Result is {0}", result);

    }

    static Dictionary<char,int> count(string s) {

        var dictionary = new Dictionary<char, int>() {

            {'A', 0},

            {'C', 0},

            {'G', 0},

            {'T', 0},

        };

        var chars = s.ToCharArray();

        foreach(char item in chars) {

            dictionary[item]++;

        }       

        return dictionary;

    }

    static bool compare(int[] lettersToReplace, int[] lettersToCompare) {

        for(int i = 0; i < lettersToReplace.Length; i++) {

            if(lettersToReplace[i]>0) {

​

                    if(lettersToReplace[i]>lettersToCompare[i]) {

                        return false;

                    }

            }

        }

        return true;

    }

    static int steadyGene(string gene) {

        //hledám nejmenší substring, který obsahuje všechna písmena, které potřebuju vyhodit

        int result = 0;

        int minLength = 0;

        var nonSteadyGeneDic = count(gene);

        var nonSteadyGene = new int[] {nonSteadyGeneDic['A'], nonSteadyGeneDic['C'], nonSteadyGeneDic['G'], nonSteadyGeneDic['T']};

        for(int k = 0; k < nonSteadyGene.Length; k++) {

            nonSteadyGene[k] = nonSteadyGene[k] - gene.Length/4;

            if(nonSteadyGene[k]>0) {

                minLength += nonSteadyGene[k];

            }

        }

        foreach(int item in nonSteadyGene) {

            Console.Write("{0}|", item);

        }

        Console.WriteLine();

        Console.WriteLine("minLength = {0}", minLength);

        Console.WriteLine("gene.Length = {0}", gene.Length);

        if(minLength==0) return result;

        int i = (gene.Length-minLength)/2+minLength;

        int min = minLength;

        int max = gene.Length;

        while(i <= gene.Length && min != max && i>=minLength) {

            Console.WriteLine("i = {0}", i);

            bool containsAllLetters = false;

            Dictionary<char, int> lettersToCompareDic = new Dictionary<char, int>();

            char firstChar = 'X';

            for(int j = 0; j <= gene.Length - i; j++) {

                string substring = gene.Substring(j,i);

                if(lettersToCompareDic.Count == 0) {

                    lettersToCompareDic = count(substring);

                    firstChar = substring[0];

                }                       

                else {

                    lettersToCompareDic[substring[substring.Length-1]]++;

                    lettersToCompareDic[firstChar]--;

                    firstChar = substring[0];

                }

                var lettersToCompare = new int[] {lettersToCompareDic['A'], lettersToCompareDic['C'], lettersToCompareDic['G'], lettersToCompareDic['T']};      

                Console.Write("{0}|",lettersToCompareDic['A']);

                Console.Write("{0}|",lettersToCompareDic['C']);

                Console.Write("{0}|",lettersToCompareDic['G']);

                Console.Write("{0}|",lettersToCompareDic['T']);

                Console.Write("{0}|",lettersToCompareDic['A']+lettersToCompareDic['C']+lettersToCompareDic['G']+lettersToCompareDic['T']);

                Console.WriteLine();

                containsAllLetters = compare(nonSteadyGene, lettersToCompare);

                if(containsAllLetters) {

                    Console.WriteLine("tru");

                    max = i;

                    if(i!=minLength) {

                        i = (i-minLength)/2+minLength;  

                    }

                    break;

                }

            }

            if(!containsAllLetters && i!=gene.Length) {

                i = (max-i)/2+i+1;

                min = i;    

                Console.WriteLine("zvetsene i = {0}",i);

            }

        }

        Console.WriteLine(min);

        Console.WriteLine(max);

        return max;         

​

    }

}