Sharing answer codes of mine about HackerRank: Bear and Steady Gene.

HackerRank: Bear and Steady Gene (in Algorithm)

Problem Statement

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

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

Note: A substring of a string \(S\) is a subsequence made up of zero or more consecutive characters of \(S\).

Answer Code (in Python3)

  • Time complexity: \(O(n^2)\)
#!/bin/python3

import sys
from collections import Counter as ctr
import math

def steadyGene(gene):
    # let's get input
    n = len(gene)
    cnt = ctr(gene)
    
    # If all element is less than n/4, substring length is 0
    if all(e<=n/4 for e in cnt.values()):
        return 0
    
    minSub = math.inf
    cnted = 0
    # Find the last sequence of the string satisfying the condition
    for i in range(n):
        cnt[gene[i]] -= 1
        while all(e<=n/4 for e in cnt.values()) and cnted <= i:
            minSub = min(minSub, i-cnted+1)
            cnt[gene[cnted]]+=1
            cnted += 1   
    return minSub    

if __name__ == "__main__":
    n = int(input().strip())
    gene = input().strip()
    result = steadyGene(gene)
    print(result)

You May Also Enjoy