We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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();
}
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.
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.
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 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")));
}
COPIED the editorial code & tried to run the sample test case but it keeps on showing message "assertion failed on line 20"
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.
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.
anybody? on how to solve this one ? completly unable to understand editorial.