# 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$$.

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

import sys
from collections import Counter as ctr
import math

# 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()