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 .
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
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.
Print the length of the minimum length substring that can be replaced to make stable.
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))