Cerinta completa

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

Subtask

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

Limbajul de programare folosit: python3

Cod:

#!/bin/python3

from collections import Counter

def steadyGene(gene):
    n = len(gene)
    target = n // 4
    cnt = Counter(gene)
    if all(cnt[ch] <= target for ch in 'ACGT'):
        return 0
    ans = n
    l = 0
    for r, ch in enumerate(gene):
        cnt[ch] -= 1
        while l <= r and all(cnt[c] <= target for c in 'ACGT'):
            ans = min(ans, r - l + 1)
            cnt[gene[l]] += 1
            l += 1
    return ans

if __name__ == '__main__':
    _ = int(input().strip())
    gene = input().strip()
    print(steadyGene(gene))

Scor obtinut: 1.0

Submission ID: 464591398

Link challenge: https://www.hackerrank.com/challenges/bear-and-steady-gene/problem

Bear and Steady Gene