Bear and Steady Gene

Sort by

recency

|

5 Discussions

|

  • + 0 comments

    import java.io.; import java.math.; import java.security.; import java.text.; import java.util.; import java.util.concurrent.; import java.util.function.; import java.util.regex.; import java.util.stream.*; import static java.util.stream.Collectors.joining; import static java.util.stream.Collectors.toList;

    class Result {

    public static int steadyGene(String gene) { 
        int a =0, c=0, g=0, t=0;
        for(int i=0; i<gene.length(); i++)
        {
            if(gene.charAt(i)=='A')a+=1;
            else if(gene.charAt(i)=='C')c+=1;
            else if(gene.charAt(i)=='G')g+=1;
            else t+=1;
        }
        int n = gene.length()/4;
        int A =0, C = 0, G = 0, T = 0, tot = 0;
        if(a>n)
        {
            A = a-n;tot+=A;
        }
        if(c>n)
        {
            C = c-n;tot+=C;
        }
        if(g>n)
        {
            G = g-n;tot+=G;
        }
        if(t>n)
        {
            T = t-n;tot+=T;
        } 
        while(true)
        {
            String s= gene.substring(0, tot+1);
            a=0;c=0;g=0;t=0;
            for(int i=0; i<tot; i++)
            {
                if(s.charAt(i)=='A')a+=1;
                else if(s.charAt(i)=='C')c+=1;
                else if(s.charAt(i)=='G')g+=1;
                else t+=1;
            }
            for(int i=0; i<gene.length()-tot; i++)
            {
                if(i>0)
                { 
                    if(gene.charAt(i-1)=='A')a-=1;
                    else if(gene.charAt(i-1)=='C')c-=1;
                    else if(gene.charAt(i-1)=='G')g-=1;
                    else t-=1;
    
                    if(gene.charAt(i+tot-1)=='A')a+=1;
                    else if(gene.charAt(i+tot-1)=='C')c+=1;
                    else if(gene.charAt(i+tot-1)=='G')g+=1;
                    else t+=1;
                }
                if(a>=A && c>=C && g>=G && t>=T)
                {
                    return tot;
                }
            }
            tot++;
            if(tot>gene.length())
            break;
        }
        return 0;   
    }
    

    }

    public class Solution { public static void main(String[] args) throws IOException { BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int n = Integer.parseInt(bufferedReader.readLine().trim());
    
        String gene = bufferedReader.readLine();
    
        int result = Result.steadyGene(gene);
    
        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();
    
        bufferedReader.close();
        bufferedWriter.close();
    }
    

    }

  • + 0 comments

    COPIED the editorial code & tried to run the sample test case but it keeps on showing message "assertion failed on line 20"

  • + 0 comments

    As mentioned in the editorial, idea is, except the "sub string" to be removed, rest of the string state should be steady (i.e each charecter count less than n/4). The string is not steady due to fact that, one or many of ACTG letter is more than n/4.

    Solution is - Keep removing letters from original string till you get a string where state is steady. i.e the charecters count is less than n/4.

    In the solution, "j" counter in while loop keeps removing charecters (by reducing the count).

    During this removal, we might have removed few necessary charecters which are still needed. This charecter is added back at the end of for loop, to get the optimal solution.

  • + 0 comments

    newts: Let's say N == 40. This means that in final string you would need to have exactly 10 A, 10 C, 10 G and 10 T.

    Now let's say that you have 9 A, 11 C, 8 G, and 12 T in initial string. Then you would need to get rid of (convert) 1 C and 2 T. Since you can replace them with any other char, all you need to find - the shortest substring that has simultaneously 1 C and 2 T.

  • + 0 comments

    anybody? on how to solve this one ? completly unable to understand editorial.

No more comments