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 .


  • is divisible by


  • in tests worth  points.

Output Format

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

Sample Input


Sample Output



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:
        while all(count2[c]>=count[c] for c in count):
        k = min(k,j-i+1)
    return k
n = int(input())
gene = input()

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]