You've successfully subscribed to The Poor Coder | Hackerrank Solutions
Great! Next, complete checkout for full access to The Poor Coder | Hackerrank Solutions
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.

## Hackerrank - Bear and Steady Gene Solution

Beeze Aal

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

• 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
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))