Hackerrank - Bear and Steady Gene Solution
2 min read

Hackerrank - Bear and Steady Gene Solution

Hackerrank - Bear and Steady Gene Solution

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

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

Constraints

  • is divisible by

Subtask

  • in tests worth  points.

Output Format

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

Sample Input

8  
GAAATAAA

Sample Output

5

Explanation

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

Solution in Python

from collections import Counter,defaultdict
def steadyGene(gene) :
    n = len(gene)
    count = Counter(gene)
    
    for k,v in count.items():
        count[k] = 0 if v <= n//4 else v-n//4
    if not sum(count.values()): return 0

    count += Counter()
    count2 = Counter()
    j = 0
    
    i, j, k = 0, 0, n

    while j<n:
        while j<n and count2 & count != count:
            count2[gene[j]]+=1
            j+=1
        while all(count2[c]>=count[c] for c in count):
            count2[gene[i]]-=1
            i+=1
        k = min(k,j-i+1)
    return k
    
n = int(input())
gene = input()
print(steadyGene(gene))

Enjoying these posts? Subscribe for more


Adblocker detected! Please consider reading this notice.

We've detected that you are using AdBlock Plus or some other adblocking software which is preventing the page from fully loading.

That's okay. But without advertising-income, we can't keep making this site awesome.

We don't have any banner, Flash, animation, obnoxious sound, or popup ad. We do not implement these annoying types of ads!

We need money to operate the site, and almost all of it comes from our online advertising.

Please add thepoorcoder.com to your ad blocking whitelist or disable your adblocking software.

×