You've successfully subscribed to The Poor Coder | Hackerrank Solutions
Great! Next, complete checkout for full access to The Poor Coder | Hackerrank Solutions
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Hackerrank Bear and Steady Gene Solution

Hackerrank Bear and Steady Gene Solution

Beeze Aal
Beeze Aal

.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

A gene is represented as a string of length  (where  is divisible by ), composed of the letters , , , and . It is considered to be steady if each of the four letters occurs exactly  times.  For example,  and  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 .  It is not necessarily steady.  Fortunately, Limak can choose one (maybe empty) substring of  and replace it with any string of the same length.

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

Note: A substring of a string  is a subsequence made up of zero or more contiguous characters of .

As an example, consider .  The substring  just before or after  can be replaced with  or .  One selection would create .

Function Description

Complete the  function in the editor below.  It should return an integer that represents the length of the smallest substring to replace.

steadyGene has the following parameter:

  • gene: a string

Input Format.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

The first line contains an interger  divisible by , that denotes the length of a string .
The second line contains a string  of length .

Constraints.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

  • is divisible by

Subtask

  • in tests worth ¬†points.

Output Format.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

Print the length of the minimum length substring that can be replaced to make  stable.

Sample Input.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue}

8  
GAAATAAA

Sample Output.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue}

5

Explanation.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

One optimal solution is to replace  with  resulting in .
The replaced substring has length .

Solution in java8

Approach 1.

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

public class Solution {

    static int steadyGene(String gene) {
        // Complete this function
        int[] chars = new int[26];
        int len = gene.length();
        int expected = gene.length() / 4;
        int overflow = 0;
        
        for (int i = 0; i < len; i++) {
            chars[gene.charAt(i) - 65]++;
        }
        
        ArrayList<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < 26; i++) {
            if (chars[i] > expected) {
                overflow += chars[i] - expected;
                list.add(i);
            }
        }
        
        int min = gene.length();
        for (int i = 0; i < len; i++) {
            for (int j = i + overflow; j < len + 1; j++) {
                if (isValidReplacement(gene.substring(i, j), list, chars, expected)) {
                    if (j - i < min) {
                        min = j - i;
                    }
                }
            }
        }
        
        return min;
    }
    
    
    public static boolean isValidReplacement(String s, ArrayList<Integer> list, int[] chars, int expected) {
        int[] counts = new int[26];
        
        for (int i = 0; i < s.length(); i++)  {
            counts[s.charAt(i) - 65]++;
        }
        
        for (int i = 0; i < list.size(); i++) {
            if (chars[list.get(i)] - counts[list.get(i)] > expected) {
                return false;
            }
        }
        
        return true;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        String gene = in.next();
        int result = steadyGene(gene);
        System.out.println(result);
        in.close();
    }
}

Approach 2.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Solution {

    static int steadyGene(String gene) {
        char[] chars = {'A', 'C', 'T', 'G'};
        int[] counts = {0, 0, 0, 0};

        Map<Character, Integer> charCounts = new HashMap<>();
        for (char c : gene.toCharArray()) {
            counts[charToInt(c)]++;
        }

        int min = Integer.MAX_VALUE;
        for (int i = 0; i < gene.length(); i++) {
            int[] counts2 = Arrays.copyOf(counts, 4);
            for (int j = i; j < gene.length(); j++) {
                int diff = j - i + 1;
                if (diff > min) {
                    break;
                }

                char c = gene.charAt(j);
                counts2[charToInt(c)]--;

                boolean ok = true;
                for (int count : counts2) {
                    if (count > gene.length() / 4) {
                        ok = false;
                        break;
                    }
                }
                if (ok) {
                    if (diff < min) {
                        min = diff;
                    }
                    break;
                }
            }
        }

        return min;
    }

    static int charToInt(char c) {
        int i;
        switch (c) {
            case 'A': i = 0; break;
            case 'C': i = 1; break;
            case 'T': i = 2; break;
            case 'G': i = 3; break;
            default: return -1;
        }
        return i;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        String gene = in.next();
        int result = steadyGene(gene);
        System.out.println(result);
        in.close();
    }
}

Approach 3.

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

public class Solution {
    
    static boolean balanced(int[] freqs, int minFreq) {
        if(freqs['A'-'A'] == minFreq 
           && freqs['C'-'A'] == minFreq
           && freqs['T'-'A'] == minFreq
           && freqs['G'-'A'] == minFreq) {
            return true;
        }
        return false;
    }
    
    static int steadyGene(String gene) {
        int[] freq = new int[26];
        
        int maxFreq = 0;
        // count freq of each letter
        for(int i=0; i<gene.length(); i++) {
            freq[gene.charAt(i)-'A']++;
        }
        
        int minFreq = gene.length()/4;
        for(int i=0; i<26; i++) {
            if(freq[i] < minFreq)
                freq[i] = minFreq;
            if(freq[i] > maxFreq)
                maxFreq = freq[i];
        }
        
        //System.out.println(Arrays.toString(freq));
        
        for(int w=maxFreq-minFreq; w<gene.length(); w++) {
            for(int i=0; i+w<=gene.length(); i++) {
                int[] newFreq = new int[26];
                for(int j=0; j<26; j++)
                    newFreq[j] = freq[j];
                String subString = gene.substring(i, i+w);
                //System.out.println(subString);
                for(int j=0; j<subString.length(); j++) {
                    if(freq[subString.charAt(j)-'A'] > minFreq) {
                        newFreq[subString.charAt(j)-'A']--;
                    }
                }
                //System.out.println("newFreq "+Arrays.toString(newFreq));
                if(balanced(newFreq, minFreq)) {
                    return w;
                }
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        String gene = in.next();
        int result = steadyGene(gene);
        System.out.println(result);
        in.close();
    }
}

Solution in python3

Approach 1.

x = int(input());s = input() 
dic = {'A': 0, 'T': 0, 'C': 0, 'G': 0}
for i in s:dic[i] += 1
x = len(s);n = x / 4;i = 0;j = 0;min = x
if dic['A'] == n and dic['T'] == n and dic['C'] == n and dic['G'] == n:print(0)
else:
    while i < x and j < x:
        while (dic['A'] > n or dic['C'] > n or dic['T'] > n or dic['G'] > n) and i < x:dic[s[i]] -= 1;i += 1
        while dic['A'] <= n and dic['C'] <= n and dic['T'] <= n and dic['G'] <= n:dic[s[j]] += 1;j += 1
        if i - j < min:
            min = i - j + 1
    print(min)

Approach 2.

import sys
n=int(input())
str1=input()
l1=[]
l2=[]
l3=[]
l4=[]
count=[str1.count('A'),str1.count('T'),str1.count('C'),str1.count('G')]
kkk=['A','T','C','G']
for x in range(len(count)):
    if((n//4)-count[x]<0):
        l1.append(kkk[x])
        l2.append(count[x]-(n//4))
    if((n//4)-count[x]>0):
        l3.append((n//4)-count[x])
for x in range(max(sum(l2),sum(l3)),n-1):
    for y in range(n-x):
        jj=list(str1[y:y+x:])
        flag=0
        for i in range(len(l1)):
            if(jj.count(l1[i])!=l2[i]):
                flag=1
                break
            else:
                flag=0
        if(flag==0):
            print(x)
            sys.exit()
        
    
    

Approach 3.

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the steadyGene function below.
def steadyGene(gene):
    n = len(gene) / 4
    gene_l = ['A', 'C', 'T', 'G']
    count_l = [gene.count(letter) for letter in gene_l]
    minlen = int(sum([n - count for count in count_l if count < n]))
    valid = False
    while valid == False:
        for i in range(len(gene) - minlen):
            selection = gene[i:i + minlen]
            count_select = [selection.count(letter) for letter in gene_l]
            subtract = [count_l[i] - count_select[i] for i in range(len(count_l))]
            valid = all(x <= n for x in subtract)
            if valid == True:
                break
        if valid == False:
            minlen += 1
    return minlen

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input())

    gene = input()

    result = steadyGene(gene)

    fptr.write(str(result) + '\n')

    fptr.close()

Solution in cpp

Approach 1.

#include <bits/stdc++.h>

using namespace std;

bool validityCheck(map<char, int> dict, int limit) {
  if (dict['A'] <= limit && dict['C'] <= limit && dict['G'] <= limit &&
      dict['T'] <= limit) {
    return true;
  } else {
    return false;
  }
}

int main() {
  int N, maxIndex = 0, out = 999999;
  map<char, int> dict;
  string str;
  cin >> N >> str;
  int limit = N / 4;
  for (int i = N - 1; i >= 0; i--) {
    dict[str[i]]++;
    if (!validityCheck(dict, limit)) {
      maxIndex = i + 1;
      dict[str[i]]--;
      break;
    }
  }
  for (int minIndex = -1;
       minIndex < N - 1 && maxIndex < N && minIndex < maxIndex; minIndex++) {
    while (!validityCheck(dict, limit) && maxIndex < N) {
      dict[str[maxIndex]]--;
      maxIndex++;
    }
    if (maxIndex > N || !validityCheck(dict, limit)) {
      break;
    }
    int substringLength = max(0, maxIndex - minIndex - 1);
    if (substringLength < out) {
      out = substringLength;
    }
    dict[str[minIndex + 1]]++;
  }
  cout << out << endl;
  return 0;
}

Approach 2.

#include<bits/stdc++.h>
using namespace std;

bool validityCheck(map<char, int> dict, int limit){
    if(dict['A'] <= limit && dict['C'] <= limit && dict['G'] <= limit && dict['T'] <= limit){
        return true;
    }else{
       return false;
    }
}

int main() {
    int N, maxIndex = 0, out = 999999;
    map<char, int> dict;
    string str;
    cin >> N >> str;
    int limit = N / 4;
    for (int i = N - 1; i >= 0; i--){
        dict[str[i]]++;
        if(!validityCheck(dict, limit)){
            maxIndex = i + 1;
            dict[str[i]]--;
            break;
        }
    }
    for(int minIndex = -1; minIndex < N - 1 && maxIndex < N && minIndex < maxIndex; minIndex++){
        while(!validityCheck(dict, limit) && maxIndex < N){
            dict[str[maxIndex]]--;
            maxIndex++;
        }
         if(maxIndex > N || !validityCheck(dict, limit)){
            break;
        }
        int substringLength = max(0, maxIndex - minIndex - 1);
        if(substringLength < out){
            out = substringLength;
        }
        dict[str[minIndex + 1]]++;
    }
    cout << out << endl;
    return 0;
}

Approach 3.

#include <bits/stdc++.h>

using namespace std;

// Complete the steadyGene function below.
int steadyGene(string gene) {
     int n=gene.size();
     map<char, int> mp;
     for(auto c: gene)
         ++mp[c];
     vector<char> genes = {'A', 'C', 'T', 'G' };
     int required = n/4;
     vector<char> neg;
     int total=0;
     for(auto c: genes)
     {
         mp[c] -= required;
         if(mp[c]<=0)
             neg.push_back(c);
         else
             total += mp[c];
     }
     for(auto x: neg)
         mp.erase(x);
     if(mp.size()==0)
         return 0;
     //for(auto p: mp)
     //    cout<<p.first<<": "<<p.second<<endl;
     //cout<<"total="<<total<<endl;
     int i=0, j=0;
     int window=n;
     int count=0;
     for(int j=0;j<n;++j)
     {
        if(mp.count(gene[j])==0)
            continue;
        --mp[gene[j]];
        if(mp[gene[j]]>=0)
            ++count;
        //cout<<"count="<<count<<endl;
        while(total==count)
        {
            window = min(window, j-i+1);
            if(mp.count(gene[i]))
            {
                ++mp[gene[i]];
                if(mp[gene[i]]>0)
                    --count;
            }
            ++i;
        }
     }
     return window;
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    int n;
    cin >> n;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');

    string gene;
    getline(cin, gene);

    int result = steadyGene(gene);

    fout << result << "\n";

    fout.close();

    return 0;
}