Sign in Subscribe
By Vishal Basumatary in Hackerrank —

Hackerrank Bear and Steady Gene Solution

Hackerrank Bear and Steady Gene Solution

.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;
}

Subscribe to The Poor Coder | Algorithm Solutions

Don’t miss out on the latest issues. Sign up now to get access to the library of members-only issues.
[email protected]
Subscribe