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

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

Note: A substring of a string $\boldsymbol{\mathrm{~S~}}$ is a subsequence made up of zero or more contiguous characters of $\boldsymbol{\mathrm{~S~}}$.

As an example, consider $\textit{gene}=\textit{ACTGAAAG}$.  The substring $\boldsymbol{AA}$ just before or after $\mbox{G}$ can be replaced with $\textit{CT}$ or $\boldsymbol{TC}$.  One selection would create $\textbf{ACTGACTG}$.

Function Description

Complete the $\textit{steadyGene}$ 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 $n$ divisible by $4$, that denotes the length of a string $\textit{gene}$. 

The second line contains a string $\textit{gene}$ of length $n$.

Constraints

$4\leq n\leq500000$  
$n$ is divisible by $4$  
$gene[i]\in[CGAT]$  

Subtask  

$4\leq n\leq2000$ in tests worth $30\%$ points.

Output Format

Print the length of the minimum length substring that can be replaced to make $\textit{gene}$ stable.

Sample Input
8  
GAAATAAA

Sample Output
5

Explanation

One optimal solution is to replace $\textbf{AAATA}$ with $\textbf{TTCCG}$ resulting in $\textbf{GTTCCGAA}$. 

The replaced substring has length $5$.

Source: hackerrank | Difficulty: MEDIUM
Tags: String algorithms


Solutions:
def solve(S, n):
	count = {}
	for c in S:
		count[c] = count.get(c, 0) + 1
	for c in count:
		if count[c] > n // 4:
			count[c] = count[c] - n // 4
		else:
			count[c] = 0
	if sum((count[c] for c in count)) == 0:
		return 0
	count2 = {}
	(i, j, best) = (0, 0, n)
	while j < n:
		while j < n and any((count2.get(c, 0) < count[c] for c in count)):
			count2[S[j]] = count2.get(S[j], 0) + 1
			j += 1
		while all((count2.get(c, 0) >= count[c] for c in count)):
			count2[S[i]] = count2.get(S[i], 0) - 1
			i += 1
		if j - i + 1 < best:
			best = j - i + 1
	return best
n = int(input())
S = input()
print(solve(S, n))


from collections import defaultdict
length = int(input())
S = input()
prefix = {}
suffix = {}
prefix[-1] = defaultdict(int)
suffix[len(S)] = defaultdict(int)

def deep_copy(o):
	copy = defaultdict(int)
	for (k, v) in o.items():
		copy[k] = v
	return copy
for (i, c) in enumerate(S):
	prefix[i] = deep_copy(prefix[i - 1])
	prefix[i][c] += 1
for (i, c) in reversed(list(enumerate(S))):
	suffix[i] = deep_copy(suffix[i + 1])
	suffix[i][c] += 1
res = length / 4 * 3
average = length / 4
for i in range(-1, len(S)):
	for j in range(min(int(i + res + 1), length), i, -1):
		ifSatisfy = True
		for g in ['A', 'C', 'T', 'G']:
			if prefix[i][g] + suffix[j][g] > average:
				ifSatisfy = False
		if ifSatisfy:
			if j - i - 1 < res:
				res = j - i - 1
		else:
			break
print(int(res))


n = int(input())
S = input()
my_dict = {}
my_dict['A'] = -n // 4
my_dict['G'] = -n // 4
my_dict['C'] = -n // 4
my_dict['T'] = -n // 4
for letter in S:
	my_dict[letter] += 1
current = {'A': 0, 'C': 0, 'G': 0, 'T': 0}
current[S[0]] += 1
best_length = len(S)
right = 0
left = 0
while right < len(S) and (my_dict['A'] != 0 or my_dict['C'] != 0 or my_dict['G'] != 0 or (my_dict['T'] != 0)):
	if current['A'] >= my_dict['A'] and current['C'] >= my_dict['C'] and (current['G'] >= my_dict['G']) and (current['T'] >= my_dict['T']):
		best_length = min(best_length, right - left + 1)
		current[S[left]] -= 1
		left += 1
	else:
		right += 1
		if right < len(S):
			current[S[right]] += 1
if (my_dict['A'] != 0 or my_dict['C'] != 0 or my_dict['G'] != 0 or (my_dict['T'] != 0)) == False:
	best_length = 0
print(best_length)


s_len = int(input().strip())
max_count = int(s_len / 4)
s = input().strip()
greedy = []
greedy_count = []
if s.count('A') > max_count:
	greedy.append('A')
	greedy_count.append(s.count('A') - max_count)
if s.count('C') > max_count:
	greedy.append('C')
	greedy_count.append(s.count('C') - max_count)
if s.count('G') > max_count:
	greedy.append('G')
	greedy_count.append(s.count('G') - max_count)
if s.count('T') > max_count:
	greedy.append('T')
	greedy_count.append(s.count('T') - max_count)
if len(greedy) == 0:
	print(0)
	quit()
start = -1
end = 0
min_chars = -1
greedy_len = len(greedy)
for n in range(s_len):
	if s[n] in greedy:
		if start == -1:
			start = n
		for k in range(greedy_len):
			if s[n] == greedy[k]:
				greedy_count[k] -= 1
				break
		sub_start = 0
		if greedy_len == 1 and greedy_count[0] < 1 or (greedy_len == 2 and greedy_count[0] < 1 and (greedy_count[1] < 1)) or (greedy_len == 3 and greedy_count[0] < 1 and (greedy_count[1] < 1) and (greedy_count[2] < 1)):
			if min_chars == -1 or min_chars > n - start + 1:
				min_chars = n - start + 1
			for k in range(greedy_len):
				if s[start] == greedy[k]:
					greedy_count[k] += 1
			sub_start = start + 1
			start = -1
			stop = False
			while sub_start < n:
				if s[sub_start] in greedy:
					start = sub_start
					stop = True
					if greedy_len == 1 and greedy_count[0] < 1 or (greedy_len == 2 and greedy_count[0] < 1 and (greedy_count[1] < 1)) or (greedy_len == 3 and greedy_count[0] < 1 and (greedy_count[1] < 1) and (greedy_count[2] < 1)):
						if min_chars == -1 or min_chars > n - start + 1:
							min_chars = n - start + 1
						for k in range(greedy_len):
							if s[sub_start] == greedy[k]:
								if greedy_count[k] + 1 < 1:
									greedy_count[k] += 1
									stop = False
								else:
									break
					if stop:
						break
				sub_start += 1
			if start == -1:
				start = n
print(min_chars)


from collections import Counter
n = int(input().strip())
m = int(n / 4)
s = input().strip()
scount = Counter(s)
genedict = {}
Anum = scount['A']
Cnum = scount['C']
Gnum = scount['G']
Tnum = scount['T']
Arem = max(0, Anum - m)
Crem = max(0, Cnum - m)
Grem = max(0, Gnum - m)
Trem = max(0, Tnum - m)
min_rem = Arem + Crem + Grem + Trem
if min_rem == 0:
	print(0)
else:
	mincount = n
	genedict['A'] = 0
	genedict['C'] = 0
	genedict['G'] = 0
	genedict['T'] = 0
	start = -1
	finish = 0
	finishflag = True
	while finish < n:
		if finishflag:
			genedict[s[finish]] += 1
			if genedict['A'] >= Arem and genedict['C'] >= Crem and (genedict['G'] >= Grem) and (genedict['T'] >= Trem):
				if finish - start < mincount:
					mincount = finish - start
				finishflag = False
				start += 1
			else:
				finish += 1
		else:
			genedict[s[start]] -= 1
			if genedict['A'] < Arem or genedict['C'] < Crem or genedict['G'] < Grem or (genedict['T'] < Trem):
				if finish - start + 1 < mincount:
					mincount = finish - start + 1
				finishflag = True
				finish += 1
			else:
				start += 1
	start += 1
	while start < finish - min_rem + 1:
		genedict[s[start]] -= 1
		if genedict['A'] < Arem or genedict['C'] < Crem or genedict['G'] < Grem or (genedict['T'] < Trem):
			if finish - start + 1 < mincount:
				mincount = finish - start + 1
			break
		start += 1
	print(mincount)


import sys

def countACGT(s):
	return [s.count('A'), s.count('C'), s.count('G'), s.count('T')]

def letterIndex(l):
	if l == 'A':
		return 0
	elif l == 'C':
		return 1
	elif l == 'G':
		return 2
	else:
		return 3
n = int(input().strip())
s = input().strip()
needACGT = [int(i - n / 4) for i in countACGT(s)]
needToHave = [max(i, 0) for i in needACGT]
if all([needToHave[i] == 0 for i in range(4)]):
	print(0)
else:
	start = 0
	end = sum(needToHave) - 1
	hasFound = countACGT(s[start:end + 1])
	while all([hasFound[i] >= needToHave[i] for i in range(4)]) == False:
		hasFound[letterIndex(s[end + 1])] += 1
		end += 1
	minLength = end - start + 1
	for i in range(end + 1, n):
		hasFound[letterIndex(s[i])] += 1
		hasFound[letterIndex(s[start])] -= 1
		start += 1
		while all([hasFound[i] >= needToHave[i] for i in range(4)]) == True:
			hasFound[letterIndex(s[start])] -= 1
			start += 1
			minLength -= 1
	print(minLength + 1)


import collections
import random
BASES = ['G', 'A', 'T', 'C']

def linear(s):
	best = len(s)
	target = len(s) // 4
	counts = {}
	for ch in BASES:
		if s.count(ch) > target:
			counts[ch] = s.count(ch) - target
		else:
			counts[ch] = 0
	best = len(s)
	left = 0
	right = 0
	while True:
		while max(counts.values()) > 0:
			if right >= len(s):
				return best
			counts[s[right]] -= 1
			right += 1
		while max(counts.values()) <= 0:
			if left >= len(s):
				return best
			if right - left < best:
				best = right - left
			counts[s[left]] += 1
			left += 1

def main():
	input()
	s = input()
	print(linear(s))
main()


from collections import Counter
n = int(input())
m = n // 4
s = input()
cnt = {'G': 0, 'A': 0, 'C': 0, 'T': 0}
cnt.update(Counter(s))
if all(map(lambda x: x == m, cnt.values())):
	print(0)
	exit()
(low, high) = (0, n)
while high - low > 1:
	mid = (high + low) // 2
	cnt_tmp = dict(cnt)
	for i in range(mid):
		cnt_tmp[s[i]] -= 1
	if all(map(lambda x: x <= m, cnt_tmp.values())):
		high = mid
		continue
	for i in range(mid, n):
		cnt_tmp[s[i - mid]] += 1
		cnt_tmp[s[i]] -= 1
		if all(map(lambda x: x <= m, cnt_tmp.values())):
			high = mid
			break
	else:
		low = mid
print(high)


n = int(input())
s = input()
d = dict()
for c in s:
	d[c] = d.setdefault(c, 0) + 1
for c in d:
	d[c] = d[c] - n / 4
d = dict(((c, d[c]) for c in d if d[c] > 0))
i = 0
j = 0
cd = dict.fromkeys('ATGC', 0)
ans = n
while j < n:
	cd[s[j]] += 1
	if all((cd[c] >= d[c] for c in d)):
		while i <= j:
			if s[i] in d and cd[s[i]] <= d[s[i]]:
				break
			cd[s[i]] -= 1
			i += 1
		ans = min(ans, j - i + 1)
	j += 1
print(ans)


n = int(input())
sequence = [char for char in input()]
stat = {}
replace_list = {}
for char in sequence:
	stat[char] = 1 if char not in stat else stat[char] + 1
for (letter, num) in stat.items():
	if num > n / 4:
		replace_list[letter] = int(num - n / 4)
if len(replace_list) == 0:
	print(0)
else:
	start = 0
	max_value = 500000
	start = 0
	end = 0
	queue = []
	for char in sequence:
		end += 1
		if char in replace_list:
			replace_list[char] -= 1
		while end - start > 1:
			if sequence[start] not in replace_list:
				start += 1
			elif replace_list[sequence[start]] < 0:
				replace_list[sequence[start]] += 1
				start += 1
			else:
				break
		if all((value <= 0 for value in replace_list.values())):
			max_value = min(end - start, max_value)
	print(max_value)


L = int(input().strip())
gn = input().strip()
from copy import copy

def find_candidate_ss(s, c):
	cpy = Counter()
	(i, j) = (0, 0)
	while c - cpy:
		cpy[s[j]] += 1
		j += 1
	L = float('inf')
	while j < len(s):
		if cpy - c:
			diff = cpy - c
			while diff[s[i]] and i < j:
				cpy[s[i]] -= 1
				diff[s[i]] -= 1
				i += 1
		if not c - cpy:
			L = min(L, j - i)
		cpy[s[j]] += 1
		j += 1
	return L
if not gn:
	exit()
from collections import Counter
gc = Counter(gn)
candidates = Counter()
for (k, v) in gc.items():
	if v - L / 4 > 0:
		candidates[k] = v - L / 4
print(find_candidate_ss(gn, candidates))


stable_amount = int(input().strip()) // 4
gene_str = input().strip()

def get_genes_to_remove(gene_str):
	freq = {'A': 0, 'T': 0, 'C': 0, 'G': 0}
	for g in gene_str:
		freq[g] += 1
	return dict([(l, f - stable_amount) for (l, f) in freq.items() if f > stable_amount])

def is_valid(genes_to_remove):
	for (l, f) in genes_to_remove.items():
		if f > 0:
			return False
	return True

def add_gene(idx, gene_str, extra):
	if gene_str[idx] in extra:
		extra[gene_str[idx]] += 1
	return extra

def remove_gene(idx, gene_str, extra):
	if gene_str[idx] in extra:
		extra[gene_str[idx]] -= 1
	return extra

def increment_end(end_idx, gene_str, genes_to_remove):
	valid_sub = False
	while valid_sub != True and end_idx < len(gene_str) - 1:
		end_idx += 1
		genes_to_remove = remove_gene(end_idx, gene_str, genes_to_remove)
		valid_sub = is_valid(genes_to_remove)
	return end_idx

def increment_start(start_idx, gene_str, genes_to_remove):
	valid_sub = True
	while valid_sub:
		genes_to_remove = add_gene(start_idx, gene_str, genes_to_remove)
		valid_sub = is_valid(genes_to_remove)
		start_idx += 1
	return start_idx

def update_solution(new_solution, curr_solution):
	if new_solution < curr_solution:
		return new_solution
	else:
		return curr_solution

def make_steady(gene_str):
	genes_to_remove = get_genes_to_remove(gene_str)
	start_idx = 0
	end_idx = 0
	valid_sub = is_valid(genes_to_remove)
	if valid_sub:
		return 0
	curr_solution = len(gene_str)
	genes_to_remove = remove_gene(start_idx, gene_str, genes_to_remove)
	valid_sub = is_valid(genes_to_remove)
	while end_idx < len(gene_str) - 1:
		end_idx = increment_end(end_idx, gene_str, genes_to_remove)
		curr_solution = update_solution(end_idx - start_idx + 1, curr_solution)
		start_idx = increment_start(start_idx, gene_str, genes_to_remove)
		curr_solution = update_solution(end_idx - start_idx + 2, curr_solution)
	valid_sub = is_valid(genes_to_remove)
	while valid_sub:
		start_idx = increment_start(start_idx, gene_str, genes_to_remove)
		curr_solution = update_solution(end_idx - start_idx + 2, curr_solution)
	return curr_solution
print(make_steady(gene_str))


from collections import Counter

def check_valid(counts, lim):
	for count in counts.values():
		if count > lim:
			return False
	return True
n = int(input())
text = input()
if n % 4 == 0:
	lim = int(n / 4)
	(head, ans) = (-1, 500000)
	counts = {}
	for char in 'AGCT':
		counts.update({char: 0})
	for index in range(n):
		counts[text[index]] += 1
		if not check_valid(counts, lim):
			head = index - 1
			counts[text[index]] -= 1
			break
	if head >= 0:
		for tail in range(n - 1, -1, -1):
			while head >= 0 and (not check_valid(counts, lim)):
				counts[text[head]] -= 1
				head -= 1
			if head >= tail or head < 0:
				break
			temp = max(0, tail - head)
			if temp < ans:
				ans = temp
			counts[text[tail]] += 1
		print(ans)
	else:
		print(0)


n = int(input())
s = list(input())
min_win = 9999999
idx = {'A': 0, 'C': 1, 'T': 2, 'G': 3}
count = [0] * 4
for each in s:
	count[idx[each]] += 1
need = [0] * 4
exp_count = int(n / 4)
for i in range(4):
	if count[i] > exp_count:
		need[i] = count[i] - exp_count
found = [0] * 4
start = 0
end = 0
l = sum(need)
c = 0
for i in range(len(s)):
	if need[idx[s[i]]] > 0:
		start = i
		end = i
		break
while start < n and end < n:
	found[idx[s[end]]] += 1
	if found[idx[s[end]]] <= need[idx[s[end]]] and need[idx[s[end]]] != 0:
		c += 1
	if c == l:
		while start <= end and (found[idx[s[start]]] > need[idx[s[start]]] or need[idx[s[start]]] == 0):
			found[idx[s[start]]] -= 1
			start += 1
		win = end - start + 1
		if win < min_win:
			min_win = win
	end += 1
print(min_win)


def counter(string):
	counts = [[0 for i in range(4)] for j in range(len(string))]
	for i in range(len(string)):
		char = string[i]
		if not i == 0:
			for j in range(4):
				counts[i][j] = counts[i - 1][j]
		if char == 'A':
			counts[i][0] += 1
		elif char == 'T':
			counts[i][1] += 1
		elif char == 'G':
			counts[i][2] += 1
		else:
			counts[i][3] += 1
	return counts

def substract(l1, l2):
	l = []
	for i in range(4):
		l.append(l1[i] - l2[i])
	return l

def add(l1, l2):
	l = []
	for i in range(4):
		l.append(l1[i] + l2[i])
	return l

def counter2(counts, s, e, n):
	l1 = substract(counts[n - 1], counts[e])
	l2 = counts[s - 1]
	l = add(l1, l2)
	for i in range(4):
		if l[i] > n / 4:
			return False
	return True
n = int(input(''))
string = input('')
counts = counter(string)
s = 1
e = 0
Rs = 1
Re = 0
candidates = []
if counts[n - 1] == [n / 4, n / 4, n / 4, n / 4]:
	print(0)
else:
	while s < n + 1 and e < n:
		if Rs == s:
			if counter2(counts, s, e, n):
				Re = e
				s = s + 1
			else:
				Re = e
				e = e + 1
		elif counter2(counts, s, e, n):
			Rs = s
			s = s + 1
		else:
			candidates.append(e - s + 2)
			Rs = s
			e = e + 1
	print(min(candidates))


from collections import defaultdict

def main():
	length = int(input())
	gene = input()
	steady_char_count = length // 4
	actg_count = defaultdict(int)
	for c in gene:
		actg_count[c] += 1
	surplus = {}
	for (k, v) in actg_count.items():
		if v > steady_char_count:
			surplus[k] = v - steady_char_count
	if len(surplus) == 0:
		print('0')
		return
	min_sequence = length
	sequence_count = defaultdict(int)
	leading_idx = 0
	trailing_idx = 0
	while leading_idx < length:
		sequence_count[gene[leading_idx]] += 1
		while is_replaceable_sequence(sequence_count, surplus):
			min_sequence = min(min_sequence, leading_idx - trailing_idx + 1)
			sequence_count[gene[trailing_idx]] -= 1
			trailing_idx += 1
		leading_idx += 1
	print(min_sequence)

def is_replaceable_sequence(sequence_count, surplus):
	is_replaceable = True
	for (k, v) in surplus.items():
		if v > sequence_count[k]:
			is_replaceable = False
			break
	return is_replaceable
main()


from collections import Counter
import sys
n = int(sys.stdin.readline())

def find_shortest_containing(gene, sub_freqs, max_sub):
	first = 0
	last = 0
	while last < len(gene):
		while last < len(gene) and any((v > 0 for v in sub_freqs.values())):
			if gene[last] in sub_freqs:
				sub_freqs[gene[last]] -= 1
			last += 1
		while first < len(gene) and all((v <= 0 for v in sub_freqs.values())):
			first += 1
			if gene[first - 1] in sub_freqs:
				sub_freqs[gene[first - 1]] += 1
		max_sub = min(max_sub, last - first + 1)
	return max_sub

def shortest_replace(gene):
	count = Counter(gene)
	num_bases = len(gene)
	expected = int(num_bases / 4)
	ideal = Counter({'A': expected, 'G': expected, 'T': expected, 'C': expected})
	most_bases = max(count.items(), key=lambda t: t[1])
	max_replace = most_bases[1] * 4 - num_bases
	change = count - ideal
	if not change:
		print(0)
	else:
		print(find_shortest_containing(gene, change, max_replace))
gene = sys.stdin.readline().strip()
shortest_replace(gene)


import sys
from collections import Counter
n = int(input())
s = input()
actg = {'A': 0, 'C': 0, 'T': 0, 'G': 0}
for s_i in s:
	actg[s_i] += 1
target = len(s) // 4
for i in 'ACTG':
	actg[i] = max(actg[i] - target, 0)
	if actg[i] == 0:
		del actg[i]
if sum(actg.values()) == 0:
	print(0)
else:
	maxlen = len(s)
	(start, end) = (0, 0)
	while end < len(s):
		if s[end] in actg.keys():
			actg[s[end]] = actg[s[end]] - 1
			if not any((i > 0 for i in actg.values())):
				while s[start] not in actg.keys() or actg[s[start]] + 1 <= 0:
					if s[start] in actg.keys():
						actg[s[start]] += 1
					start += 1
				maxlen = min(maxlen, end - start + 1)
		end += 1
	print(maxlen)


from collections import Counter

def valid(ctr, n):
	return all(v <= n)

def solve(xs, n):

	def valid(ctr):
		return all((v <= n // 4 for v in ctr.values()))
	ctr = Counter(xs)
	if valid(ctr):
		return 0
	min_so_far = n
	j = 0
	for (i, x) in enumerate(xs):
		ctr[x] -= 1
		while valid(ctr) and j <= i:
			min_so_far = min(min_so_far, i - j + 1)
			ctr[xs[j]] += 1
			j += 1
	return min_so_far

def main():
	n = int(input())
	xs = input()
	print(solve(xs, n))

def get_random_dna(n=10):
	import random
	return ''.join(('ATGC'[random.randint(0, 3)] for _ in range(n * 4)))
main()


(n, s) = (int(input()), input())
need = n // 4
cnts = {'A': 0, 'C': 0, 'G': 0, 'T': 0}
(left, right) = (0, n - 1)
while cnts[s[right]] < need:
	cnts[s[right]] += 1
	right -= 1
mini = right - left
while right < n - 1 and left < right:
	if cnts[s[left]] < need:
		cnts[s[left]] += 1
		left += 1
	else:
		right += 1
		cnts[s[right]] -= 1
	mini = min(mini, right - left)
print(mini + 1)


import random

def steady_substr(gene_len, gene):
	frequencies = {'A': 0, 'T': 0, 'C': 0, 'G': 0}
	min_len = float('inf')
	chars_needed = {}
	for nt in gene:
		frequencies[nt] += 1
	for i in frequencies:
		if frequencies[i] > gene_len // 4:
			chars_needed[i] = frequencies[i] - gene_len // 4
	if not chars_needed:
		return 0
	start = 0
	for end in range(gene_len):
		if gene[end] in chars_needed:
			chars_needed[gene[end]] -= 1
		if all((i <= 0 for i in chars_needed.values())):
			min_len = min(min_len, end - start + 1)
			while start <= end:
				if gene[start] in chars_needed:
					chars_needed[gene[start]] += 1
				if not all((i <= 0 for i in chars_needed.values())):
					chars_needed[gene[start]] -= 1
					break
				else:
					start += 1
					min_len = min(min_len, end - start + 1)
	return min_len
print(steady_substr(int(input()), input()))


length = int(input().strip())
string = input().strip().upper()
each_char_count = length // 4
last_pos = 0
start_post = 0
out_length = length
char_map = {'G': 0, 'A': 0, 'T': 0, 'C': 0}

def steady_string():
	if char_map['G'] <= each_char_count and char_map['T'] <= each_char_count and (char_map['A'] <= each_char_count) and (char_map['C'] <= each_char_count):
		return True
	else:
		return False
for indx in range(length - 1, -1, -1):
	char_map[string[indx]] = char_map[string[indx]] + 1
	if not steady_string():
		char_map[string[indx]] = char_map[string[indx]] - 1
		last_pos = indx + 1
		break
for indx in range(length):
	char_map[string[indx]] = char_map[string[indx]] + 1
	while not steady_string() and last_pos < length:
		char_map[string[last_pos]] = char_map[string[last_pos]] - 1
		last_pos = last_pos + 1
	if not steady_string():
		break
	substring_length = last_pos - indx - 1
	if substring_length < out_length:
		out_length = substring_length
if out_length == length:
	print(0)
else:
	print(out_length)


def specs(string, n):
	d = dict.fromkeys(['A', 'T', 'C', 'G'], 0)
	for x in string:
		d[x] += 1
	expected_count = n / 4
	for letter in d.keys():
		d[letter] = max(0, d[letter] - expected_count)
	return d

def meet_specs(specs_string, specs_substring):
	for x in ['A', 'T', 'C', 'G']:
		if specs_string[x] < specs_substring[x]:
			return False
	return True

def steady_dna(s, n):
	d_substr = specs(s, n)
	if sum(d_substr.values()) == 0:
		return 0
	d = dict.fromkeys(['A', 'T', 'C', 'G'], 0)
	minimal_length = n
	i = 0
	j = 0
	while j < n:
		d[s[j]] += 1
		has_possible_substring = False
		while meet_specs(d, d_substr) and i <= j:
			minimal_length = min(minimal_length, j - i + 1)
			d[s[i]] -= 1
			i += 1
		j += 1
	return minimal_length
n = int(input())
s = input()
print(steady_dna(s, n))


def find(array, n):
	change_cnts = [0, 0, 0, 0]
	for i in array:
		change_cnts[i] += 1
	change_cnts = [i - int(n / 4) if i > n / 4 else 0 for i in change_cnts]
	change_cnt = sum(change_cnts)
	if change_cnt < 2:
		return change_cnt
	(i, j) = (0, 0)
	cnts = [1 if i == array[0] else 0 for i in range(4)]
	min_size = n
	while True:
		if len([i for i in range(4) if not cnts[i] >= change_cnts[i]]) == 0:
			min_size = min(j - i + 1, min_size)
			if j - i + 1 > change_cnt:
				i += 1
				cnts[array[i - 1]] -= 1
			else:
				break
		elif j - 1 + 1 >= min_size:
			i += 1
			j += 1
			if j >= n:
				break
			cnts[array[i - 1]] -= 1
			cnts[array[j]] += 1
		else:
			j += 1
			if j >= n:
				break
			cnts[array[j]] += 1
	return min_size
n = int(input())
d = {'A': 0, 'C': 1, 'T': 2, 'G': 3}
array = [d[i] for i in input()]
print(find(array, n))


def main():
	input()
	s = input()
	counts = Counter()
	for c in s:
		counts[c] += 1
	c_to_remove = {}
	c_average = len(s) / 4
	for c in ['A', 'C', 'T', 'G']:
		c_to_remove[c] = counts[c] - c_average
	counts = Counter()
	i_start = 0
	i_end = 0
	len_min = float('inf')
	best_interval = (0, 0)
	while True:
		if is_valid(counts, c_to_remove):
			len_cur = i_end - i_start
			if len_cur < len_min:
				len_min = len_cur
				best_interval = (i_start, i_end)
			if i_start != i_end:
				counts[s[i_start]] -= 1
				i_start += 1
			else:
				i_end += 1
		else:
			if i_end == len(s):
				break
			counts[s[i_end]] += 1
			i_end += 1
	print(len_min)

def is_valid(counts, counts_needed):
	for (c, count) in counts_needed.items():
		if counts[c] < count:
			return False
	return True

class Counter:

	def __init__(self):
		self.table = {}

	def __getitem__(self, key):
		return self.table.get(key, 0)

	def __setitem__(self, key, value):
		self.table[key] = value
main()


import sys
LETTERS = 'ACGT'
length = int(sys.stdin.readline())
gene = sys.stdin.readline().strip()
el = length // 4
counts = [gene.count(l) for l in LETTERS]
b = e = 0
result = length
while b < length:
	valid = all([c <= el for c in counts])
	if not valid and e < length:
		counts[LETTERS.index(gene[e])] -= 1
		e += 1
	else:
		if valid:
			result = min(result, e - b)
		counts[LETTERS.index(gene[b])] += 1
		b += 1
print(result)


from collections import deque

class DequeCounter:
	st_num = None

	def __init__(self, right_list, left_list):
		self.right_potential = deque(right_list)
		self.right = deque()
		self.left_potential = deque(left_list)
		self.left = deque()
		self.max_len = 0
		if DequeCounter.st_num is None:
			DequeCounter.st_num = len(right_list) // 4
		self.ctr = {k: 0 for k in 'AGTC'}

	def consume_all_possible_right(self):
		while self.right_potential:
			next_char = self.right_potential[0]
			if self.ctr[next_char] < DequeCounter.st_num:
				self.ctr[next_char] += 1
				self.right.append(self.right_potential.popleft())
			else:
				break
		self.max_len = self.tot_length()

	def consume_all_possible_left(self):
		while self.left_potential:
			next_char = self.left_potential[-1]
			if self.ctr[next_char] < DequeCounter.st_num:
				self.ctr[next_char] += 1
				self.left.appendleft(self.left_potential.pop())
				self.max_len = max(self.tot_length(), self.max_len)
			else:
				break

	def give_up_right_till(self):
		while self.right and self.left_potential:
			rc = self.right.pop()
			self.ctr[rc] -= 1
			if rc == self.left_potential[-1] or not self.right:
				self.consume_all_possible_left()
				if self.max_potential_len() < self.max_len:
					break

	def set_max_left(self, max_left_len):
		num_to_chop = len(self.left_potential) + len(self.left) - max_left_len
		for __ in range(num_to_chop):
			self.left_potential.popleft()

	def max_potential_len(self):
		return len(self.left_potential) + self.tot_length()

	def tot_length(self):
		return len(self.right) + len(self.left)

	def dts(self, d):
		return ''.join((e for e in d))

	def deques(self):
		return [self.left_potential, self.left, self.right, self.right_potential]

	def str(self):
		return '|'.join((self.dts(d) for d in self.deques()))

	def short_str(self):
		return '|'.join((self.dts(d) for d in self.deques()[1:3]))

	def vss(self):
		l = [self.tot_length(), len(self.left), len(self.right), self.max_potential_len(), self.max_len]
		if self.tot_length() < 500:
			l.append(self.str())
		return ':'.join((str(e) for e in l))

def make_steady(a, b):
	ca = DequeCounter(a, a)
	ca.consume_all_possible_right()
	cb = DequeCounter(b, b)
	cb.consume_all_possible_right()
	ca.set_max_left(cb.max_len)
	cb.set_max_left(ca.max_len)
	ca.consume_all_possible_left()
	cb.consume_all_possible_left()
	(long, short) = (cb, ca)
	if ca.tot_length() > cb.tot_length():
		(long, short) = (ca, cb)
	elif ca.tot_length() == cb.tot_length() and len(ca.right) > len(cb.right):
		(long, short) = (ca, cb)
	long.give_up_right_till()
	return len(a) - long.max_len
l = input().strip()
s = input().strip()
sr = list(reversed(s))
print(make_steady(s, sr))


GL = int(input())
S = GL // 4
L = input()
CountA = 0
CountT = 0
CountG = 0
CountC = 0
for k in L:
	if k == 'A':
		CountA += 1
	elif k == 'T':
		CountT += 1
	elif k == 'G':
		CountG += 1
	elif k == 'C':
		CountC += 1
CL = [CountA, CountT, CountG, CountC]
RL = []
for _ in CL:
	R = _ - S
	if R > 0:
		RL.append(R)
	else:
		RL.append(0)
StringL = 0
if CountA == CountT and CountT == CountG and (CountG == CountC):
	print('', end='')
else:
	i = 0
	CountA = 0
	CountT = 0
	CountG = 0
	CountC = 0
	while True:
		if L[i] == 'A':
			CountA += 1
		elif L[i] == 'T':
			CountT += 1
		elif L[i] == 'G':
			CountG += 1
		elif L[i] == 'C':
			CountC += 1
		else:
			print('Error')
		if CountA >= RL[0] and CountT >= RL[1] and (CountG >= RL[2]) and (CountC >= RL[3]):
			break
		else:
			i += 1
	StringL = i + 1
	StopI = i
	i = 0
	while True:
		while True:
			if L[i] == 'A':
				CountA -= 1
			elif L[i] == 'T':
				CountT -= 1
			elif L[i] == 'G':
				CountG -= 1
			elif L[i] == 'C':
				CountC -= 1
			else:
				print('Error')
			i += 1
			if CountA >= RL[0] and CountT >= RL[1] and (CountG >= RL[2]) and (CountC >= RL[3]):
				StringL = StopI - i + 1
			else:
				break
		StopI += 1
		if StopI == GL:
			break
		if L[StopI] == 'A':
			CountA += 1
		elif L[StopI] == 'T':
			CountT += 1
		elif L[StopI] == 'G':
			CountG += 1
		elif L[StopI] == 'C':
			CountC += 1
		else:
			print('Error')
print(StringL)


n = int(input())
gene = input().strip()
nbs = ['A', 'T', 'C', 'G']
limit = n / 4
left = 0
right = n - 1
out_counts = {nb: 0 for nb in nbs}
while right >= left:
	if out_counts[gene[right]] == limit:
		break
	out_counts[gene[right]] += 1
	right -= 1
best = right - left + 1
while left < n:
	while right < n - 1 and any([out_counts[nb] > limit for nb in nbs]):
		right += 1
		out_counts[gene[right]] -= 1
	if any([out_counts[nb] > limit for nb in nbs]):
		break
	cur_best = right - left + 1
	if cur_best < best:
		best = cur_best
	out_counts[gene[left]] += 1
	left += 1
print(best)


def solve(S, n):
	count = {}
	for c in S:
		count[c] = count.get(c, 0) + 1
	for c in count:
		if count[c] > n // 4:
			count[c] = count[c] - n // 4
		else:
			count[c] = 0
	if sum((count[c] for c in count)) == 0:
		return 0
	count2 = {}
	(i, j, best) = (0, 0, n)
	while j < n:
		while j < n and any((count2.get(c, 0) < count[c] for c in count)):
			count2[S[j]] = count2.get(S[j], 0) + 1
			j += 1
		while all((count2.get(c, 0) >= count[c] for c in count)):
			count2[S[i]] = count2.get(S[i], 0) - 1
			i += 1
		if j - i + 1 < best:
			best = j - i + 1
	return best
n = int(input())
S = input()
print(solve(S, n))


n = int(input().strip())
s = input().strip()
(count, indexes) = ({}, {})
for i in range(1, len(s) + 1):
	character = s[i - 1]
	if character not in indexes:
		indexes[character] = []
		count[character] = 0
	count[character] += 1
	indexes[character].append(i)
maximum_allowed = n // 4
exceeds = [x for x in count.keys() if count[x] > maximum_allowed]
remove_ranges = {}
for letter in exceeds:
	remove_ranges[letter] = []
	leave_out = len(indexes[letter]) - maximum_allowed
	ranges = maximum_allowed + 1
	for i in range(ranges):
		remove_ranges[letter].append([indexes[letter][i], indexes[letter][i + leave_out - 1]])
minimum = n
if len(exceeds) == 3:
	first = remove_ranges[exceeds[0]]
	second = remove_ranges[exceeds[1]]
	third = remove_ranges[exceeds[2]]
	range_first = first.pop(0)
	range_second = second.pop(0)
	range_third = third.pop(0)
	while True:
		range_length = max(range_first[1], range_second[1], range_third[1]) - min(range_first[0], range_second[0], range_third[0]) + 1
		if range_length < minimum:
			minimum = range_length
		if len(first) == 0 or len(second) == 0 or len(third) == 0:
			break
		if range_first[0] < range_second[0] and range_first[0] < range_third[0]:
			range_first = first.pop(0)
		elif range_second[0] < range_first[0] and range_second[0] < range_third[0]:
			range_second = second.pop(0)
		else:
			range_third = third.pop(0)
elif len(exceeds) == 2:
	first = remove_ranges[exceeds[0]]
	second = remove_ranges[exceeds[1]]
	range_first = first.pop(0)
	range_second = second.pop(0)
	while True:
		range_length = max(range_first[1], range_second[1]) - min(range_first[0], range_second[0]) + 1
		if range_length < minimum:
			minimum = range_length
		if len(first) == 0 or len(second) == 0:
			break
		if range_first[0] < range_second[0]:
			range_first = first.pop(0)
		else:
			range_second = second.pop(0)
elif len(exceeds) == 1:
	first = remove_ranges[exceeds[0]]
	for range_first in first:
		range_length = range_first[1] - range_first[0] + 1
		if range_length < minimum:
			minimum = range_length
else:
	minimum = 0
print(minimum)


def count_letters(gene_str):
	letter_counts = {'G': 0, 'A': 0, 'C': 0, 'T': 0}
	for c in gene_str:
		letter_counts[c] += 1
	return letter_counts

def has_all_needed_letters(found, needs):
	for (c, v) in found.items():
		if needs[c] > v:
			return False
	return True

def find_steady_substring_length(gene_str):
	letter_counts = count_letters(gene_str)
	gene_str_len = len(gene_str)
	steady_freq = int(gene_str_len / 4)
	needs = {c: v - steady_freq for (c, v) in letter_counts.items() if v > steady_freq}
	if not needs:
		return 0
	found = {c: 0 for c in needs}
	min_len = 999999
	i = 0
	for (j, l) in enumerate(gene_str):
		if l in needs:
			found[l] += 1
		has_all_letters = has_all_needed_letters(found, needs)
		if has_all_letters:
			while i < j:
				min_len = min(min_len, j - i + 1)
				l = gene_str[i]
				if l in needs:
					if found[l] > needs[l]:
						found[l] -= 1
					else:
						break
				i += 1
	return min_len

def main():
	input()
	gene_str = input().strip()
	length = find_steady_substring_length(gene_str)
	print(length)
main()


from collections import Counter
length = int(input())
data = input()
num = length // 4
counts = Counter(data)
totalDif = 0
for c in [i for i in counts.keys()]:
	if counts[c] > num:
		counts[c] -= num
		totalDif += counts[c]
	else:
		counts.pop(c)
if totalDif <= 1:
	print(totalDif)
else:
	start = -1
	end = -1
	for i in range(length):
		if data[i] in counts.keys():
			counts[data[i]] -= 1
			if counts[data[i]] > 0:
				if start == -1:
					start = i
			if sum([t for t in counts.values() if t > 0]) == 0:
				end = i
				break
	minSub = end - start + 1
	while end < length:
		if minSub == totalDif:
			break
		while counts[data[start]] < 0:
			counts[data[start]] += 1
			for i in range(start + 1, length - totalDif):
				if data[i] in counts.keys():
					start = i
					break
		if sum([t for t in counts.values() if t > 0]) == 0:
			minSub = min(minSub, end - start + 1)
		if data[start] in counts.keys():
			counts[data[start]] += 1
		start += 1
		while start <= length - totalDif:
			if data[start] in counts.keys():
				break
			start += 1
		end += 1
		while end < length:
			if data[end] in counts.keys():
				counts[data[end]] -= 1
				if sum([t for t in counts.values() if t > 0]) == 0:
					break
			end += 1
		if sum([t for t in counts.values() if t > 0]) == 0:
			minSub = min(minSub, end - start + 1)
	print(minSub)


from collections import Counter
n = int(input())
s = input()
c = Counter(s)
e = dict()
for k in 'ACGT':
	e[k] = max(0, c[k] - n // 4)
if max(e.values()) == 0:
	print(0)
else:
	all_ge = lambda d1, d2: all((v >= d2[k] for (k, v) in d1.items()))
	curr = {k: 0 for k in 'ACGT'}
	r = n
	start = 0
	for (i, c) in enumerate(s):
		curr[c] += 1
		if all_ge(curr, e):
			curr[s[start]] -= 1
			while all_ge(curr, e):
				start += 1
				curr[s[start]] -= 1
			curr[s[start]] += 1
			r = min(r, i - start + 1)
	print(r)


import collections

def main():
	input()
	print(Solver(input().strip()).solve())

class Solver:

	def __init__(self, inputValue):
		self.inputValue = inputValue
		self.strlen = len(inputValue)

	def solve(self):
		if not self.computeSurplus():
			return 0
		queue = collections.deque()
		candidates = self.getCandidates()
		result = 999999
		while True:
			while not self.validator.isMatchingSurplus():
				candidate = next(candidates, None)
				if candidate is None:
					return result
				queue.append(candidate)
				self.validator.add(candidate[1])
			while self.validator.isMatchingSurplus():
				result = min(result, queue[-1][0] - queue[0][0] + 1)
				if result <= 1:
					return result
				self.validator.subtract(queue.popleft()[1])
		return result

	def computeSurplus(self):
		self.validator = Validator(self.strlen // 4)
		for c in self.inputValue:
			self.validator.add(c)
		if self.validator.isSteady():
			return False
		self.validator.switchToSurplusMode()
		return True

	def getCandidates(self):

		def gen():
			for (index, value) in enumerate(self.inputValue):
				if self.validator.belongsToSurplus(value):
					yield (index, value)
		return gen()

class Validator:

	def __init__(self, bucketSize):
		self.bucketSize = bucketSize
		self.buckets = [0, 0, 0, 0]

	def add(self, obj):
		index = ord(obj) * 3 % 5
		self.buckets[index] += 1

	def subtract(self, obj):
		index = ord(obj) * 3 % 5
		self.buckets[index] -= 1

	def switchToSurplusMode(self):
		self.surplus = [0, 0, 0, 0]
		for i in range(len(self.buckets)):
			if self.buckets[i] > self.bucketSize:
				self.surplus[i] = self.buckets[i] - self.bucketSize
		self.buckets = [0, 0, 0, 0]

	def belongsToSurplus(self, obj):
		return self.surplus[ord(obj) * 3 % 5] > 0

	def isMatchingSurplus(self):
		for (index, value) in enumerate(self.surplus):
			if 0 < value > self.buckets[index]:
				return False
		return True

	def isSteady(self):
		for c in self.buckets:
			if c > self.bucketSize:
				return False
		return True
main()


def match(dict1, dict2):
	for d in dict1.keys():
		if dict1[d] < dict2[d]:
			return False
	return True
n = int(input())
gene = input()
dict = {'A': 0, 'T': 0, 'C': 0, 'G': 0}
for d in dict:
	dict[d] = gene.count(d)
size = n / 4
sum = 0
dictOver = {'A': 0, 'T': 0, 'C': 0, 'G': 0}
for i in dict.items():
	if i[1] > size:
		dictOver[i[0]] = int(i[1] - size)
temp = {'A': 0, 'T': 0, 'C': 0, 'G': 0}
min = n
i = j = 0
temp[gene[0]] += 1
while i < n and j < n:
	while not match(temp, dictOver) and j < n - 1:
		j += 1
		temp[gene[j]] += 1
	while i < n - 1:
		temp[gene[i]] -= 1
		if match(temp, dictOver):
			i += 1
		else:
			temp[gene[i]] += 1
			break
	if match(temp, dictOver):
		min_temp = j - i + 1
	if min_temp < min:
		min = min_temp
	temp[gene[i]] -= 1
	i += 1
print(min)


def check(d1, d2):
	ans = 0
	for k in d1:
		if d1[k] < d2[k]:
			ans += d2[k] - d1[k]
	return ans
l = int(input().strip())
s = input().strip()
d = {'A': 0, 'T': 0, 'G': 0, 'C': 0}
for c in s:
	d[c] += 1
for c in d:
	d[c] = max(0, d[c] - l // 4)
cl = sum(d.values())
if cl == 0:
	print(0)
	exit(0)
done = False
min_cl = l
be = 0
en = 1
ct = {'A': 0, 'T': 0, 'G': 0, 'C': 0}
ct[s[be]] += 1
while not done:
	inc = check(ct, d)
	while inc > 0:
		if en < l:
			ct[s[en]] += 1
			en += 1
			inc -= 1
			if inc == 0:
				inc = check(ct, d)
		else:
			done = True
			break
	while True:
		if ct[s[be]] == d[s[be]]:
			if en - be <= min_cl:
				min_cl = en - be
				ct[s[be]] -= 1
				be += 1
				break
			else:
				for i in range(en - be - min_cl):
					ct[s[be]] -= 1
					be += 1
				break
		elif ct[s[be]] < d[s[be]]:
			break
		else:
			ct[s[be]] -= 1
			be += 1
print(min_cl)


import sys
from collections import Counter
n = int(sys.stdin.readline())
s = sys.stdin.readline()
res = 0
c = Counter(s)
base = ['A', 'T', 'C', 'G']
bc = Counter()
bc['A'] = 0
bc['T'] = 0
bc['C'] = 0
bc['G'] = 0
for b in base:
	if c[b] > n / 4:
		bc[b] = c[b] - n / 4

def sum_counter(counter):
	m = 0
	for e in counter.values():
		m += e
	return m

def is_correct(counter):
	for b in base:
		if counter[b] < bc[b]:
			return False
	return True

def upper_bound():
	cup = Counter()
	for i in range(n):
		cup[s[i]] += 1
		if is_correct(cup):
			return i + 1

def return_sub():
	if bc.keys() == ['0'] * 4:
		return 0
	lb = 0
	up = upper_bound()
	sub = up
	cx = Counter(s[lb:up])
	while up < n:
		cx[s[lb]] -= 1
		if is_correct(cx):
			lb += 1
			if up - lb <= sub:
				sub = up - lb
		else:
			up += 1
			cx[s[lb]] += 1
			if up != n:
				cx[s[up - 1]] += 1
	return sub
sys.stdout.write(str(return_sub()))


toidx = {'A': 0, 'C': 1, 'T': 2, 'G': 3}
n = int(input())
text = input().strip()
limit = n // 4

def check_limit(arr, limit):
	return arr[0] <= limit and arr[1] <= limit and (arr[2] <= limit) and (arr[3] <= limit)
counts = [0] * 4
i = 0
for v in text:
	idx = toidx[v]
	counts[idx] += 1
	if not check_limit(counts, limit):
		counts[idx] -= 1
		break
	i += 1
if i == n:
	print(0)
else:
	i -= 1
	result = n - i - 1
	j = n - 1
	while j >= 0:
		idx = toidx[text[j]]
		counts[idx] += 1
		while i >= 0 and (not check_limit(counts, limit)):
			idx_i = toidx[text[i]]
			counts[idx_i] -= 1
			if i == 0:
				break
			i -= 1
		if not check_limit(counts, limit):
			counts[idx] -= 1
			j += 1
			break
		_result = j - i - 1
		if _result < result:
			result = _result
		if i == 0:
			break
		j -= 1
	_result = j - i - 1
	if _result < result:
		result = _result
	print(result)


import sys
n = int(input().strip())
s = input()
histo = [0] * 4
for i in range(0, len(s)):
	if s[i] == 'A':
		histo[0] += 1
	elif s[i] == 'C':
		histo[1] += 1
	elif s[i] == 'G':
		histo[2] += 1
	elif s[i] == 'T':
		histo[3] += 1
add = [0] * 4
for i in range(0, 4):
	add[i] = int(histo[i] - n / 4)
	if add[i] < 0:
		add[i] = 0
sum_of_sub = [0] * 4
min_length = 500001
if add[0] == 0 and add[1] == 0 and (add[2] == 0) and (add[3] == 0):
	min_length = 0
if min_length > 0:
	beg_index = 0
	for i in range(0, n):
		if s[i] == 'A':
			current = 0
		elif s[i] == 'C':
			current = 1
		elif s[i] == 'G':
			current = 2
		elif s[i] == 'T':
			current = 3
		sum_of_sub[current] += 1
		while sum_of_sub[0] >= add[0] and sum_of_sub[1] >= add[1] and (sum_of_sub[2] >= add[2]) and (sum_of_sub[3] >= add[3]):
			length = i + 1 - beg_index
			if length < min_length:
				min_length = length
			if s[beg_index] == 'A':
				current = 0
			elif s[beg_index] == 'C':
				current = 1
			elif s[beg_index] == 'G':
				current = 2
			elif s[beg_index] == 'T':
				current = 3
			sum_of_sub[current] -= 1
			beg_index += 1
print(min_length)


import bisect
N = int(input())
line = input().strip()
revline = line[::-1]
maxch = len(line) // 4
fl = []
bl = []
dic = {'A': 0, 'C': 0, 'T': 0, 'G': 0}
dic2 = {'A': 0, 'C': 0, 'T': 0, 'G': 0}
n = 0
while n < len(line):
	dic[line[n]] += 1
	dic2[revline[n]] += 1
	fl.append((dic['A'], dic['C'], dic['T'], dic['G']))
	bl.append((dic2['A'], dic2['C'], dic2['T'], dic2['G']))
	n += 1
Alist = [f[0] for f in bl]
Clist = [f[1] for f in bl]
Tlist = [f[2] for f in bl]
Glist = [f[3] for f in bl]
most = 0
for f in range(len(line)):
	a1 = bisect.bisect_right(Alist, maxch - fl[f][0])
	c1 = bisect.bisect_right(Clist, maxch - fl[f][1])
	t1 = bisect.bisect_right(Tlist, maxch - fl[f][2])
	g1 = bisect.bisect_right(Glist, maxch - fl[f][3])
	minback = min(a1, c1, t1, g1)
	if minback > 0:
		if f + minback + 1 > most:
			most = f + minback + 1
print(len(line) - most)


cache = []
n = int(input())
s = input()
m = {'A': 0, 'C': 1, 'T': 2, 'G': 3}
least = 1000000
nums = [0, 0, 0, 0]
cache.append(nums[:])
for i in range(n):
	nums[m[s[i]]] += 1
	cache.append(nums[:])
needed = [x - n // 4 for x in nums]

def check(nums, nums2=cache[0]):
	for i in range(4):
		if nums[i] - nums2[i] < needed[i]:
			return 0
	return 1

def bsearch(nums, start, end):
	if start == end:
		return start
	mid = (start + end + 1) // 2
	if check(nums, cache[mid]):
		return bsearch(nums, mid, end)
	else:
		return bsearch(nums, start, mid - 1)
start = 0
for i in range(n + 1):
	if check(cache[i]):
		start = bsearch(cache[i], start, i)
		least = min(least, i - start)
print(least)


n = int(input().strip())
s = input().strip()
stable_num = n // 4
total_of = {'A': 0, 'T': 0, 'G': 0, 'C': 0}
num_extra = {'A': 0, 'T': 0, 'G': 0, 'C': 0}
for ch in s:
	total_of[ch] += 1
for (letter, total) in total_of.items():
	if total > stable_num:
		num_extra[letter] = total - stable_num
letters_in_sub = {'A': 0, 'T': 0, 'G': 0, 'C': 0}

def vals_eq_or_larger(d1, d2):
	for (k, v) in d1.items():
		if d2[k] > v:
			return False
	return True
min_sublen = n
curr_len = 1
start = 0
end = 1
letters_in_sub[s[0]] += 1
while start < n and end <= n:
	if vals_eq_or_larger(letters_in_sub, num_extra):
		min_sublen = min(min_sublen, curr_len)
		letters_in_sub[s[start]] -= 1
		start += 1
		curr_len -= 1
		continue
	else:
		if end == n:
			break
		letters_in_sub[s[end]] += 1
		end += 1
		curr_len += 1
print(min_sublen)


def match(ref, test):
	for x in ref:
		if ref[x] > 0 and test[x] < ref[x]:
			return False
	return True

def first_match(S, s, b, e, curr):
	while e < len(S) - 1:
		e += 1
		curr[S[e]] = curr[S[e]] + 1
		if match(s, curr):
			return e
	return e

def reduce_left(S, s, b, e, curr):
	while b <= e:
		curr[S[b]] = curr[S[b]] - 1
		if match(s, curr):
			b += 1
		else:
			curr[S[b]] = curr[S[b]] + 1
			return b
	return b
N = input()
S = input()
expected = len(S) / 4
d = {'A': 0, 'C': 0, 'T': 0, 'G': 0}
for letter in S:
	d[letter] = d[letter] + 1
na = d['A'] - expected
nc = d['C'] - expected
nt = d['T'] - expected
ng = d['G'] - expected
s = {'A': na, 'C': nc, 'T': nt, 'G': ng}
window = {'A': 0, 'T': 0, 'G': 0, 'C': 0}
mini = 9999999999
(begin, end) = (0, 0)
window[S[0]] = 1
while end < len(S) - 1:
	end = first_match(S, s, begin, end, window)
	begin = reduce_left(S, s, begin, end, window)
	mini = min(mini, end - begin)
print(mini + 1)


N = int(input().strip())
S = input().strip()
a = sum((C == 'A' for C in S)) - N // 4
c = sum((C == 'C' for C in S)) - N // 4
g = sum((C == 'G' for C in S)) - N // 4
t = sum((C == 'T' for C in S)) - N // 4
a = a if a > 0 else 0
c = c if c > 0 else 0
g = g if g > 0 else 0
t = t if t > 0 else 0

def generate_list(C, count):
	if count == 0:
		return [i for i in range(N)]
	L = [-1 for _ in range(N)]
	idx = 0
	current_count = 0
	for i in range(N):
		if S[i] == C:
			current_count += 1
		if current_count == count:
			while S[idx] != C:
				L[idx] = i
				idx += 1
			current_count -= 1
			L[idx] = i
			idx += 1
	return L
if max([a, c, g, t]) == 0:
	print(0)
else:
	A = generate_list('A', a)
	C = generate_list('C', c)
	G = generate_list('G', g)
	T = generate_list('T', t)
	result = N
	for i in range(N):
		L = [A[i], C[i], G[i], T[i]]
		if -1 in L:
			break
		result = min(result, max(L) - i + 1)
	print(result)


(n, string) = (int(input()), input())
l = len(string)
A = [0] * 4
D = {'A': 0, 'C': 1, 'G': 2, 'T': 3}
for c in string:
	A[D[c]] += 1
deltaA = [l // 4 - x if l // 4 - x < 0 else 0 for x in A]
(dna, S, count) = ('ACGT', set(), sum(deltaA))
if count == 0:
	print(0)
	exit()
for i in range(4):
	if deltaA[i] < 0:
		S.add(dna[i])
for i in range(l):
	if string[i] in S:
		minIndex = i
		break
for i in range(minIndex, l):
	c = string[i]
	cIndex = D[c]
	if c in S:
		if deltaA[cIndex] < 0:
			deltaA[cIndex] += 1
			count += 1
			if count == 0:
				maxIndex = i
				break
		else:
			deltaA[cIndex] += 1
			if c == string[minIndex]:
				while True:
					if string[minIndex] not in S:
						minIndex += 1
						continue
					elif deltaA[D[string[minIndex]]] > 0:
						deltaA[D[string[minIndex]]] -= 1
						minIndex += 1
						continue
					else:
						break
substringMin = maxIndex - minIndex + 1
for i in range(maxIndex + 1, l):
	c = string[i]
	cIndex = D[c]
	if c in S:
		deltaA[cIndex] += 1
		if c == string[minIndex]:
			while True:
				if string[minIndex] not in S:
					minIndex += 1
					continue
				elif deltaA[D[string[minIndex]]] > 0:
					deltaA[D[string[minIndex]]] -= 1
					minIndex += 1
					continue
				else:
					break
			currentLength = i - minIndex + 1
			if currentLength < substringMin:
				substringMin = currentLength
print(substringMin)


import collections

def main():
	n = int(input())
	steady = n // 4
	s = input()
	keys = 'ACGT'
	zeroes = {}
	for key in keys:
		zeroes[key] = 0
	ins = dict(zeroes)
	for c in s:
		ins[c] += 1
	replcount = 0
	replfitcount = 0
	repls = dict(zeroes)
	for key in keys:
		diff = ins[key] - steady
		if diff > 0:
			repls[key] = diff
			replcount += diff
			replfitcount += 1

	class Fit:

		def __init__(self):
			self.fit = dict(zeroes)
			self.fitcount = 0

		def add(self, pos):
			c = s[pos]
			self.fit[c] += 1
			if repls[c] != 0 and self.fit[c] == repls[c]:
				self.fitcount += 1

		def remove(self, pos):
			c = s[pos]
			if repls[c] != 0 and self.fit[c] == repls[c]:
				self.fitcount -= 1
			self.fit[c] -= 1

		def fits(self):
			return self.fitcount >= replfitcount
	begin = 0
	size = 0
	fit = Fit()
	while size < n and (not fit.fits()):
		fit.add(begin + size)
		size += 1
	bestsize = size
	while begin + size <= n:
		if not fit.fits():
			if begin + size == n:
				break
			fit.remove(begin)
			fit.add(begin + size)
			begin += 1
		else:
			bestsize = size
			if bestsize == replcount:
				break
			size -= 1
			fit.remove(begin + size)
	print(bestsize)
main()


import sys
n = int(input())
s = input()
loc = {}
for k in 'ACGT':
	loc[k] = []
for i in range(len(s) - 1, -1, -1):
	loc[s[i]].append(i)
cnt = {}
for k in 'ACGT':
	cnt[k] = len(loc[k]) - int(n / 4)
	if cnt[k] <= 0:
		del cnt[k]
		del loc[k]
ans = sys.maxsize
if cnt:
	while True:
		l = min(loc, key=lambda x: loc[x][-1])
		u = max(loc, key=lambda x: loc[x][cnt[x] * -1])
		ans = min(ans, loc[u][cnt[u] * -1] - loc[l].pop() + 1)
		if len(loc[l]) == cnt[l]:
			break
else:
	ans = 0
print(ans)


def withinLimit(smap, limit):
	for (k, v) in smap.items():
		if v > limit:
			return False
	return True
size = int(input())
geneStr = input().strip()
steadyMap = {'A': 0, 'C': 0, 'T': 0, 'G': 0}
limit = size / 4
maxidx = 0
curmin = 1 << 28
for i in range(len(geneStr) - 1, -1, -1):
	steadyMap[geneStr[i]] += 1
	if not withinLimit(steadyMap, limit):
		steadyMap[geneStr[i]] -= 1
		maxidx = i + 1
		break
minidx = -1
while minidx < size - 1 and maxidx < size and (minidx < maxidx):
	while not withinLimit(steadyMap, limit) and maxidx < size:
		steadyMap[geneStr[maxidx]] -= 1
		maxidx += 1
	if maxidx > size or not withinLimit(steadyMap, limit):
		break
	sublen = max(0, maxidx - minidx - 1)
	if sublen < curmin:
		curmin = sublen
	steadyMap[geneStr[minidx + 1]] += 1
	minidx += 1
print(curmin)


from collections import Counter
import sys
import math
n = int(input())
s1 = input()
s = Counter(s1)
if all((e <= n / 4 for e in s.values())):
	print(0)
	sys.exit(0)
result = float('inf')
out = 0
for mnum in range(n):
	s[s1[mnum]] -= 1
	while all((e <= n / 4 for e in s.values())) and out <= mnum:
		result = min(result, mnum - out + 1)
		s[s1[out]] += 1
		out += 1
print(result)


def check(dict, limit):
	if dict.get('A') <= limit and dict.get('C') <= limit and (dict.get('G') <= limit) and (dict.get('T') <= limit):
		return True
	else:
		return False

def main():
	maxIndex = 0
	out = 999999
	dict = {'A': 0, 'C': 0, 'G': 0, 'T': 0}
	N = int(input().strip())
	s = input().strip()
	limit = N / 4
	for i in reversed(range(N)):
		dict.update({s[i]: dict.get(s[i]) + 1})
		if not check(dict, limit):
			maxIndex = i + 1
			dict.update({s[i]: dict.get(s[i]) - 1})
			break
	minIndex = -1
	while minIndex < N - 1 and maxIndex < N and (minIndex < maxIndex):
		while not check(dict, limit) and maxIndex < N:
			dict.update({s[maxIndex]: dict.get(s[maxIndex]) - 1})
			maxIndex += 1
		if maxIndex > N or not check(dict, limit):
			break
		res = max(0, maxIndex - minIndex - 1)
		if res < out:
			out = res
		dict.update({s[minIndex + 1]: dict.get(s[minIndex + 1]) + 1})
		minIndex += 1
	print(out)
main()


import sys
n = int(input())
genes = input()
d = {'A': 0, 'G': 0, 'C': 0, 'T': 0}
ave = n // 4
for i in range(len(genes)):
	gene = genes[i]
	if d[gene] == ave:
		l = i - 1
		break
	else:
		d[gene] += 1
else:
	print(0)
	sys.exit()
result = len(genes)
current_l = l
for current_r in range(len(genes) - 1, -1, -1):
	gene = genes[current_r]
	if d[gene] == ave:
		current_length = current_r - current_l
		if result > current_length:
			l = current_l
			r = current_r
			result = current_length
		if current_l == -1:
			break
	while d[gene] == ave and current_l > -1:
		d[genes[current_l]] -= 1
		current_l -= 1
	if d[gene] == ave:
		break
	else:
		d[gene] += 1
print(result)


def valid(d, limit):
	if d['A'] <= limit and d['C'] <= limit and (d['G'] <= limit) and (d['T'] <= limit):
		return True
	else:
		return False
n = int(input())
s = input()
limit = n // 4
maxIdx = 0
out = 999999
d = {i: 0 for i in 'ATGC'}
for i in range(n - 1, -1, -1):
	d[s[i]] += 1
	if not valid(d, limit):
		maxIdx = i + 1
		d[s[i]] -= 1
		break
for minIdx in range(-1, n - 1):
	if not (maxIdx < n and minIdx < maxIdx):
		break
	while not valid(d, limit) and maxIdx < n:
		d[s[maxIdx]] -= 1
		maxIdx += 1
	if maxIdx > n or not valid(d, limit):
		break
	substringlen = max(0, maxIdx - minIdx - 1)
	if substringlen < out:
		out = substringlen
	d[s[minIdx + 1]] += 1
print(out)


from collections import defaultdict, Counter

def is_valid_string(good_len, memo):
	for (k, v) in memo.items():
		if v > good_len:
			return False
	return True

def find_sub_len(full_length, string):
	good_len = full_length // 4
	ext_memo = defaultdict(int)
	t = -1
	for i in range(full_length - 1, -1, -1):
		ext_memo[string[i]] += 1
		if not is_valid_string(good_len, ext_memo):
			t = i + 1
			ext_memo[string[i]] -= 1
			break
	if t == -1:
		return 0
	current_solution = 99999999
	for h in range(-1, full_length - 1):
		if t >= full_length:
			break
		if h >= t:
			break
		while not is_valid_string(good_len, ext_memo) and t < full_length:
			ext_memo[string[t]] -= 1
			t += 1
		if t > full_length or not is_valid_string(good_len, ext_memo):
			break
		new_solution = max(0, t - h - 1)
		if new_solution == 50021:
			print(h, t, ext_memo, string[h - 1:h + 2], string[t - 1:t + 2])
		if current_solution > new_solution:
			current_solution = new_solution
		ext_memo[string[h + 1]] += 1
	return current_solution
import doctest
doctest.testmod()
full_length = int(input().strip())
string = input().strip()
print(find_sub_len(full_length, string))


def sub_to_zero(n):
	return lambda x: 0 if x < n else x - n

class Histogram:

	def __init__(self, hist=None):
		if hist is None:
			self.hist = [0] * 4
		else:
			self.hist = hist

	def add_all(self, string):
		for c in iter(string):
			self.add(c)
		return self

	def decode(self, c):
		if c == 'A':
			return 0
		elif c == 'C':
			return 1
		elif c == 'G':
			return 2
		else:
			return 3

	def add(self, c):
		self.hist[self.decode(c)] += 1

	def remove(self, c):
		self.hist[self.decode(c)] -= 1

	def to_replace(self):
		overage = sum(self.hist) // 4
		return Histogram(list(map(sub_to_zero(overage), self.hist)))

	def contains(self, other):
		for i in range(0, 4):
			if self.hist[i] < other.hist[i]:
				return False
		return True

	def size(self):
		return sum(self.hist)

	def __str__(self):
		return str(self.hist)

def find_min_stabilizing_substring(dna):
	delta = Histogram().add_all(dna).to_replace()
	if delta.size() == 0:
		return 0
	n = len(dna)
	best_len = n
	hist = Histogram()
	fi = 0
	ti = 0
	while True:
		if hist.contains(delta):
			if ti - fi < best_len:
				best_len = ti - fi
			if fi < ti:
				hist.remove(dna[fi])
				fi += 1
				continue
		if ti < n:
			hist.add(dna[ti])
			ti += 1
		else:
			break
	return best_len
n = int(input().strip())
dna = input().strip()
print(find_min_stabilizing_substring(dna))


import sys
from collections import defaultdict

def rubberband(gene, strn):
	n = int(strn)
	genecounts = defaultdict(lambda : 0)
	for l in gene:
		genecounts[l] += 1
	target = int(int(n) / 4)
	surplus_counts = {key: value - target for (key, value) in genecounts.items() if value > target}
	left = 0
	right = sum(surplus_counts.values())
	if right == 0:
		return 0
	best = n
	substring_counts = defaultdict(lambda : 0)
	for l in gene[left:right]:
		substring_counts[l] += 1
	while left < n:
		satisfied = all([substring_counts[k] >= surplus_counts[k] for k in surplus_counts])
		if satisfied:
			best = min(best, right - left)
			substring_counts[gene[left]] -= 1
			left += 1
		elif right < n:
			substring_counts[gene[right]] += 1
			right += 1
		else:
			return best
	return best
imp = sys.stdin.read().split('\n')
print(rubberband(imp[1], imp[0]))


from sys import exit
n = int(input())
s = input()
n4 = n // 4
cnts = {c: 0 for c in 'ACGT'}
for (i, c) in enumerate(s):
	nc = cnts[c] + 1
	if nc > n4:
		break
	cnts[c] = nc
else:
	print(0)
	exit(0)
for (j, c) in enumerate(s[::-1], start=1):
	nc = cnts[c] + 1
	if nc > n4:
		break
	cnts[c] = nc
j = n - j
res = j - i + 1
while i > 1:
	while i > 1:
		i -= 1
		cnts[s[i]] -= 1
		if s[i] == c:
			break
	else:
		break
	while True:
		nc = cnts[c] + 1
		if nc > n4:
			break
		cnts[c] = nc
		j -= 1
		c = s[j]
	res = min(res, j - i + 1)
print(res)


def satisfied(freq):
	for bp in base_pairs:
		if full_freq[bp] > n / 4:
			if freq[bp] < full_freq[bp] - n / 4:
				return False
	return True
n = int(input())
gene = input()
base_pairs = ['A', 'C', 'T', 'G']
full_freq = {bp: 0 for bp in base_pairs}
for nuc in gene:
	full_freq[nuc] += 1
cur_freq = {bp: 0 for bp in base_pairs}
start = end = 0
min_length = [float('inf')] * n
while start < n and full_freq[gene[start]] <= n / 4:
	start += 1
if start == n:
	print(0)
	exit(0)
cur_freq[gene[start]] += 1
end = start
while start < n:
	while end < n - 1 and (not satisfied(cur_freq)):
		end += 1
		cur_freq[gene[end]] += 1
	if satisfied(cur_freq):
		min_length[start] = end - start + 1
		cur_freq[gene[start]] -= 1
		start += 1
	if end == n - 1:
		break
	while start < end and full_freq[gene[start]] <= n / 4:
		cur_freq[gene[start]] -= 1
		start += 1
print(min(min_length))


from collections import Counter, defaultdict
n = int(input())
s = input()
counter = Counter(s)
diff = {k: v - n // 4 for (k, v) in counter.items()}
(tail, head, m) = (0, 0, n)
sub = defaultdict(int)
while True:
	if all((sub[k] >= diff[k] for k in diff)):
		if head - tail < m:
			m = head - tail
		if tail < head:
			if head == n:
				break
			sub[s[tail]] -= 1
			tail += 1
		else:
			sub[s[head]] += 1
			head += 1
	else:
		if head == n:
			break
		sub[s[head]] += 1
		head += 1
print(m)


str_len = int(input())
str = input()
min_repeated = str_len / 4
i = 0
count = {'A': 0, 'C': 0, 'T': 0, 'G': 0}
extra_count = {'A': 0, 'C': 0, 'T': 0, 'G': 0}
while i < str_len:
	count[str[i]] += 1
	i += 1
extra_count['A'] = 0 if count['A'] <= min_repeated else count['A'] - min_repeated
extra_count['C'] = 0 if count['C'] <= min_repeated else count['C'] - min_repeated
extra_count['T'] = 0 if count['T'] <= min_repeated else count['T'] - min_repeated
extra_count['G'] = 0 if count['G'] <= min_repeated else count['G'] - min_repeated
l = 0
r = 0
max_possible_len = 0
sub_str_count = {'A': 0, 'C': 0, 'T': 0, 'G': 0}
while r < str_len:
	sub_str_count[str[r]] += 1
	got_string = True
	for i in extra_count:
		if sub_str_count[i] < extra_count[i]:
			got_string = False
			break
	if got_string:
		break
	r += 1
min_len = r + 1
while True:
	sub_str_count[str[l]] -= 1
	l += 1
	got_string = True
	for i in extra_count:
		if sub_str_count[i] < extra_count[i]:
			r += 1
			sub_str_count[str[r]] += 1
			got_string = False
			break
	if got_string:
		min_len -= 1
	elif r == str_len - 1:
		break
print(min_len)


KEYS = 'ACTG'

def read_int():
	return int(input().strip())

def read_string():
	return str(input().strip())

def create_empty_dictionary():
	return {c: 0 for c in KEYS}

def fill_dictionary(dd, s):
	for c in s:
		dd[c] += 1

def find_minimal_string(count, s):

	def is_admissible_substring(loc_counter, ref_counter):
		is_admissible = True
		for k in ref_counter.keys():
			if loc_counter[k] < ref_counter[k]:
				is_admissible = False
				break
		return is_admissible
	cl = list(s)
	sl = len(s)
	min_len = sl + 1
	(best_l, best_r) = (0, 0)
	(start_l, start_r) = (0, 0)
	(curr_r, curr_l) = (0, 0)
	rc = create_empty_dictionary()
	while True:
		for curr_r in range(start_r, sl):
			rc[cl[curr_r]] += 1
			if is_admissible_substring(rc, count):
				curr_len = curr_r - curr_l + 1
				if curr_len < min_len:
					min_len = curr_len
					(best_r, best_l) = (curr_r, curr_l)
				start_r = curr_r + 1
				break
		for curr_l in range(start_l, start_r + 1):
			if is_admissible_substring(rc, count):
				curr_len = curr_r - curr_l + 1
				if curr_len < min_len:
					min_len = curr_len
					(best_r, best_l) = (curr_r, curr_l)
				start_l = curr_l + 1
			else:
				break
			rc[cl[curr_l]] -= 1
		if curr_r == sl - 1:
			break
	return (min_len, best_l, best_r)
n = read_int()
s = read_string()
counter = create_empty_dictionary()
fill_dictionary(counter, s)
average = len(s) // 4
already_ok = True
for c in KEYS:
	counter[c] -= average
	if counter[c] != 0:
		already_ok = False
if already_ok:
	print(0)
else:
	(length, i, j) = find_minimal_string(counter, s)
	print(length)


from collections import Counter
n = int(input())
sequence = input()
cnt = Counter(sequence)

def cmp_cnt(a, b):
	for i in a:
		if a[i] > b[i]:
			return False
	return True
cnt = Counter({w: cnt[w] - n / 4 for w in cnt if cnt[w] > n / 4})
(i, j) = (0, 0)
shortest = 999999
current_cnt = Counter()
if cnt != Counter():
	while j < n:
		while not cmp_cnt(cnt, current_cnt) and j < n:
			current_cnt[sequence[j]] += 1
			j += 1
		while cmp_cnt(cnt, current_cnt):
			shortest = min(shortest, j - i)
			if i < j:
				current_cnt[sequence[i]] -= 1
			i += 1
			if i > j:
				current_cnt[sequence[j]] += 1
				j += 1
else:
	shortest = 0
print(shortest)


from collections import Counter

def solve(s):
	c = Counter(s)
	n = len(s) // 4
	sp = 0
	ep = 0
	best = len(s)
	while ep < len(s):
		if max(c.values()) > n:
			c[s[ep]] = c[s[ep]] - 1
			ep = ep + 1
		else:
			best = min(best, ep - sp)
			c[s[sp]] = c[s[sp]] + 1
			sp = sp + 1
	return best
meh = input()
print(solve(input()))


import sys
from collections import Counter
n = int(input().strip())
s = input().strip()
ct = Counter(list(s))
tgt = n / 4
A = ct['A']
T = ct['T']
G = ct['G']
C = ct['C']
mA = int(ct['A'] - tgt)
mT = int(ct['T'] - tgt)
mG = int(ct['G'] - tgt)
mC = int(ct['C'] - tgt)
m = {'A': mA, 'T': mT, 'G': mG, 'C': mC}
start_len = max(mA, mT, mG, mC)
start_index = 0
end_index = start_len
min_len = len(s)
s1 = s[start_index:end_index]
ct1 = Counter(list(s1))
while ct1['A'] < mA or ct1['T'] < mT or ct1['G'] < mG or (ct1['C'] < mC):
	end_index = end_index + 1
	s1 = s[start_index:end_index]
	key = s[end_index - 1]
	ct1[key] = ct1[key] + 1
key = s[start_index]
while ct1[s[start_index]] - 1 >= m[s[start_index]]:
	key = s[start_index]
	ct1[key] = ct1[key] - 1
	start_index = start_index + 1
if end_index - start_index < min_len:
	min_len = end_index - start_index
while end_index < len(s) - 1:
	end_index = end_index + 1
	s1 = s[start_index:end_index]
	k = s[end_index - 1]
	ct1[k] = ct1[k] + 1
	if s[end_index - 1] == s[start_index]:
		l = s[start_index]
		ct1[l] = ct1[l] - 1
		start_index = start_index + 1
		key = s[start_index]
		while ct1[key] - 1 >= m[key]:
			ct1[key] = ct1[key] - 1
			start_index = start_index + 1
			key = s[start_index]
			if end_index - start_index < min_len:
				min_len = end_index - start_index
print(min_len)


from collections import Counter
import sys
import math
n = int(input())
s1 = input()
s = Counter(s1)
if all((e <= n / 4 for e in s.values())):
	print(0)
	sys.exit(0)
result = float('inf')
out = 0
for mnum in range(n):
	s[s1[mnum]] -= 1
	while all((e <= n / 4 for e in s.values())) and out <= mnum:
		result = min(result, mnum - out + 1)
		s[s1[out]] += 1
		out += 1
print(result)


import sys

def validityCheck(d, limit):
	if d['A'] <= limit and d['C'] <= limit and (d['G'] <= limit) and (d['T'] <= limit):
		return True
	else:
		return False
n = int(input().strip())
s = list(input().strip())
maxIndex = 0
out = 999999
d = {'A': 0, 'C': 0, 'G': 0, 'T': 0}
limit = int(n / 4)
for i in range(n - 1, -1, -1):
	d[s[i]] += 1
	if not validityCheck(d, limit):
		maxIndex = i + 1
		d[s[i]] -= 1
		break
minIndex = -1
while minIndex < n - 1 and maxIndex < n and (minIndex < maxIndex):
	while not validityCheck(d, limit) and maxIndex < n:
		d[s[maxIndex]] -= 1
		maxIndex += 1
	if maxIndex > n or not validityCheck(d, limit):
		break
	substringLength = max([0, maxIndex - minIndex - 1])
	if substringLength < out:
		out = substringLength
	d[s[minIndex + 1]] += 1
	minIndex += 1
print(out)


import collections
l = int(input().strip())
w = input().strip()
c = collections.Counter(w)
optimal = int(l / 4)
m = {'A': optimal, 'G': optimal, 'T': optimal, 'C': optimal}
for (k, v) in c.items():
	m[k] -= v
minlength = 0
for v in m.values():
	if v < 0:
		minlength += -v
negs = {}
for (k, v) in m.items():
	if v < 0:
		negs[k] = v
minwin = l

def iszero(m):
	for v in m.values():
		if v < 0:
			return False
	return True
(start, end) = (0, 0)
(bstart, bend) = (0, 0)
lastc = None
allpos = None
for i in range(l - minlength):
	if w[i] not in negs:
		continue
	allpos = False
	lastc = w[i]
	start = i
	c = None
	if not iszero(negs):
		for j in range(end, l):
			c = w[j]
			if c not in negs:
				continue
			negs[c] += 1
			if iszero(negs):
				allpos = True
				break
		end = j + 1
	else:
		allpos = True
	if allpos and end - start < minwin:
		minwin = end - start
		(bstart, bend) = (start, end)
	negs[lastc] -= 1
print(bend - bstart)


import math

def valid(data, limit):
	for v in data.values():
		if v > limit:
			return False
	return True
n = int(input().strip())
average = int(n / 4)
gene = input().strip()
d = dict([('A', 0), ('C', 0), ('G', 0), ('T', 0)])
leftHand = -1
rightHand = n - 1
smallest = average * 3
while valid(d, average):
	d[gene[rightHand]] += 1
	rightHand -= 1
	if not valid(d, average):
		rightHand += 1
		d[gene[rightHand]] -= 1
		break
while leftHand <= rightHand and rightHand < n:
	while not valid(d, average) and rightHand < n - 1:
		rightHand += 1
		d[gene[rightHand]] -= 1
	if not valid(d, average) or rightHand >= n - 1:
		break
	currentSubStringLength = rightHand - leftHand
	if currentSubStringLength < smallest:
		smallest = currentSubStringLength
	leftHand += 1
	d[gene[leftHand]] += 1
print(smallest)


from collections import Counter
from copy import copy
n = int(input())
target = n // 4
s = input()
counter = Counter(s)
needle = {}
for (letter, count) in counter.items():
	if count > target:
		needle[letter] = count - target
if not needle:
	print(0)
	exit()
positions = {}
for key in needle:
	positions[key] = []
	for (i, c) in enumerate(s):
		if key == c:
			positions[key].append(i)
indexes = {c: [0, size] for (c, size) in needle.items()}

def checklimits(positions, indexes):
	for key in positions:
		if len(positions[key]) > indexes[key][1]:
			return True
	return False

def getmove(positions, indexes):
	return min([key for (key, value) in positions.items() if indexes[key][1] < len(value)], key=lambda key: positions[key][indexes[key][0]])

def getsize(positions, indexes):
	return max([positions[key][indexes[key][1] - 1] for key in indexes]) - min([positions[key][indexes[key][0]] for key in indexes]) + 1
result = getsize(positions, indexes)
while checklimits(positions, indexes):
	move = getmove(positions, indexes)
	indexes[move][0] += 1
	indexes[move][1] += 1
	result = min(result, getsize(positions, indexes))
print(result)


n = int(input())
limit = n / 4
s = input()
counter = {'A': 0, 'T': 0, 'C': 0, 'G': 0}
the_max = 0
for i in range(n):
	if counter[s[i]] < limit:
		counter[s[i]] += 1
		the_max += 1
	else:
		break
total = the_max
try:
	for j in range(n - 1, -1, -1):
		if counter[s[j]] < limit:
			counter[s[j]] += 1
			total += 1
		else:
			the_max = max(the_max, total)
			while True:
				if i == 0:
					raise ValueError
				elif s[i - 1] == s[j]:
					i -= 1
					break
				else:
					counter[s[i - 1]] -= 1
					total -= 1
					i -= 1
except ValueError:
	pass
the_max = max(the_max, total)
print(n - the_max)


from collections import Counter

def desired_letter_count(text):
	return int(len(text) / 4)

def excessive_letters(text, letter_occurances):
	letters = {'A': 0, 'C': 0, 'G': 0, 'T': 0}
	letters.update({l: freq - letter_occurances for (l, freq) in Counter(text).items() if freq > letter_occurances})
	return letters

def excessive_genes(genes):
	return excessive_letters(genes, desired_letter_count(genes))

def gene_stabilized(replace_me):
	for freq in replace_me.values():
		if freq > 0:
			return False
	return True

def there_is_more_symbols(text, position):
	return position < len(text)

def min_substring(text):
	replace_me = excessive_genes(text)
	if sum(replace_me.values()) == 0:
		return 0
	pos_r = 0
	pos_l = 0
	min_length = 10000000
	while there_is_more_symbols(text, pos_r):
		while there_is_more_symbols(text, pos_r) and (not gene_stabilized(replace_me)):
			symbol = text[pos_r]
			replace_me[symbol] -= 1
			pos_r += 1
		while gene_stabilized(replace_me):
			symbol = text[pos_l]
			replace_me[symbol] += 1
			pos_l += 1
		if pos_r - pos_l + 1 < min_length:
			min_length = pos_r - pos_l + 1
	return min_length

def main():
	n = int(input())
	s = input()
	print(min_substring(s))
main()


from collections import Counter

def is_steady(c):
	return c['A'] == c['C'] == c['T'] == c['G']

def max_char_count_leq(counter, max_count):
	return len(counter) == 0 or (counter['A'] <= max_count and counter['C'] <= max_count and (counter['T'] <= max_count) and (counter['G'] <= max_count))

def main(N, s):
	substr_end = 0
	max_char_count = int(N / 4)
	min_substr_len = N
	counter = Counter()
	for i in reversed(range(N)):
		if not max_char_count_leq(counter, max_char_count):
			substr_end = i + 1
			break
		else:
			counter[s[i]] += 1
	substr_start = 0
	while substr_start <= substr_end and substr_start < N:
		while not max_char_count_leq(counter, max_char_count) and substr_end < N:
			counter[s[substr_end]] -= 1
			substr_end += 1
		substr_len = substr_end - substr_start
		if substr_len < min_substr_len:
			min_substr_len = substr_len
		if substr_end >= N:
			break
		counter[s[substr_start]] += 1
		substr_start += 1
	print(min_substr_len)
N = int(input())
s = input()
main(N, s)


n = int(input())
gene = input()
need = n // 4
letterCount = {'G': 0, 'A': 0, 'C': 0, 'T': 0}
T = 0
H = 0
for i in range(0, n):
	if letterCount[gene[i]] == n // 4:
		H = i
		break
	else:
		letterCount[gene[i]] += 1
letterCount = {'G': 0, 'A': 0, 'C': 0, 'T': 0}
for i in range(1, n + 1):
	if letterCount[gene[-i]] == n // 4:
		T = n - i
		break
	else:
		letterCount[gene[-i]] += 1
h = 0
t = T
mini = t - h
for i in range(H + 1):
	if letterCount[gene[i]] == n // 4:
		while t < n - 1 and gene[t + 1] != gene[i]:
			t += 1
			letterCount[gene[t]] -= 1
		t += 1
	else:
		letterCount[gene[i]] += 1
	if mini > t - i:
		mini = t - i
print(mini)


from collections import Counter

def minsteady(s):
	normal = len(s) // 4
	over = Counter(s)
	for (char, count) in list(over.items()):
		x = over[char] - normal
		if x > 0:
			over[char] = x
		else:
			del over[char]
	if not over:
		return 0
	current = Counter()
	start = 0
	while over[s[start]] == 0:
		start += 1
	stop = start
	while True:
		current[s[stop]] += 1
		if all((current[c] >= over[c] for c in over)):
			break
		stop += 1
	best = stop - start + 1
	for stop in range(stop + 1, len(s)):
		current[s[stop]] += 1
		while current[s[start]] > over[s[start]]:
			current[s[start]] -= 1
			start += 1
		best = min(best, stop - start + 1)
	return best
size = int(input())
s = input().strip()
assert len(s) == size
print(minsteady(s))


import re
length = int(input())
str1 = input()
charIndex = ['', 'A', 'T', 'C', 'G']
arr = {'A': 0, 'C': 0, 'T': 0, 'G': 0}
l = int(len(str1) / 4)
replaceStr = ''
findStr = ''
findArr = {'A': 0, 'C': 0, 'G': 0, 'T': 0}

def validCheck(arr, limit):
	if arr['A'] <= limit and arr['C'] <= limit and (arr['T'] <= limit) and (arr['G'] <= limit):
		return True
	else:
		return False
minl = 9999999
maxI = 0
i = length - 1
while i >= 0 and validCheck(arr, l) == True:
	arr[str1[i]] += 1
	i -= 1
maxI = i + 1
minI = -1
while minI < length - 1 and minI < maxI and (maxI < length):
	while validCheck(arr, l) == False and maxI < length:
		arr[str1[maxI]] -= 1
		maxI += 1
	if maxI >= length or validCheck(arr, l) == False:
		break
	subStringLen = max(0, maxI - minI - 1)
	if subStringLen < minl:
		minl = subStringLen
	arr[str1[minI + 1]] += 1
	minI += 1
print(minl)


import sys
gene = {'A': 0, 'C': 1, 'G': 2, 'T': 3}
n = int(input().strip())
genecum = [[0] * (n + 1) for _ in gene]
s = input().strip()
for pos in range(n):
	genecum[gene[s[pos]]][pos + 1] = 1
	for g in genecum:
		g[pos + 1] += g[pos]
exceed = [max(g[-1] - n // 4, 0) for g in genecum]
minspan = n
p_start = 0
for p_end in range(n + 1):
	while p_start <= p_end and all((genecum[g][p_end] - genecum[g][p_start] >= exceed[g] for g in range(4))):
		minspan = min(minspan, p_end - p_start)
		p_start += 1
print(minspan)


from collections import Counter
import sys
import math
n = int(input())
s1 = input()
s = Counter(s1)
if all((e <= n / 4 for e in s.values())):
	print(0)
	sys.exit(0)
result = float('inf')
out = 0
for mnum in range(n):
	s[s1[mnum]] -= 1
	while all((e <= n / 4 for e in s.values())) and out <= mnum:
		result = min(result, mnum - out + 1)
		s[s1[out]] += 1
		out += 1
print(result)


def atLeastExcess(f, excess):
	for key in f:
		if excess[key] > 0 and f[key] < excess[key]:
			return False
	return True

def minToSteady(s):
	k = len(s) / 4
	freq = {'A': 0, 'T': 0, 'G': 0, 'C': 0}
	excess = {'A': 0, 'T': 0, 'G': 0, 'C': 0}
	for letter in s:
		freq[letter] += 1
	for key in freq:
		if freq[key] > k:
			excess[key] = int(freq[key] - k)
	numDel = 0
	for key in excess:
		if excess[key] > 0:
			numDel += excess[key]
	if numDel <= 1:
		return numDel
	minLen = len(s)
	front = end = 0
	f = {'A': 0, 'T': 0, 'G': 0, 'C': 0}
	prev = len(s)
	while front <= end and front < len(s):
		while not atLeastExcess(f, excess) and end < len(s):
			if prev != end:
				f[s[end]] += 1
			if atLeastExcess(f, excess):
				if end - front + 1 < minLen:
					minLen = end - front + 1
				break
			end += 1
		prev = end
		if atLeastExcess(f, excess) and end - front + 1 < minLen:
			minLen = end - front + 1
		f[s[front]] -= 1
		front += 1
	return minLen

def main():
	n = int(input().strip())
	inputStr = input().strip()
	print(minToSteady(inputStr))
main()


n = int(input())
s = input().strip().lower()
defficit_dict = {}
defficit_dict['a'] = -n // 4
defficit_dict['g'] = -n // 4
defficit_dict['c'] = -n // 4
defficit_dict['t'] = -n // 4
for char in s:
	defficit_dict[char] += 1
current = {'a': 0, 'c': 0, 'g': 0, 't': 0}
current[s[0]] += 1
best_length = len(s)
right = 0
left = 0
while right < len(s) and (defficit_dict['a'] != 0 or defficit_dict['c'] != 0 or defficit_dict['g'] != 0 or (defficit_dict['t'] != 0)):
	if current['a'] >= defficit_dict['a'] and current['c'] >= defficit_dict['c'] and (current['g'] >= defficit_dict['g']) and (current['t'] >= defficit_dict['t']):
		best_length = min(best_length, right - left + 1)
		current[s[left]] -= 1
		left += 1
	else:
		right += 1
		if right < len(s):
			current[s[right]] += 1
if (defficit_dict['a'] != 0 or defficit_dict['c'] != 0 or defficit_dict['g'] != 0 or (defficit_dict['t'] != 0)) == False:
	best_length = 0
print(best_length)


from collections import defaultdict
import sys
N = int(input().strip())
S = input().strip()
sSet = defaultdict(int)
for c in S:
	sSet[c] += 1
for k in sSet.keys():
	sSet[k] -= N // 4
for k in ['G', 'T', 'C', 'A']:
	if k not in sSet:
		sSet[k] = -N // 4
if sum([abs(f) for (c, f) in sSet.items()]) == 0:
	print(0)
	sys.exit()
(begin, end, minbegin, minend) = (0, -1, -1, -1)
cSet = defaultdict(int)
minlength = len(S)

def checkCondition(currentSet, originalSet):
	for k in originalSet.keys():
		if originalSet[k] > 0 and currentSet[k] < originalSet[k]:
			return False
	return True
while end < len(S) - 1:
	end += 1
	cSet[S[end]] += 1
	while not checkCondition(cSet, sSet) and end < len(S) - 1:
		end += 1
		cSet[S[end]] += 1
	cSet[S[begin]] -= 1
	begin += 1
	while checkCondition(cSet, sSet) and begin <= end:
		cSet[S[begin]] -= 1
		begin += 1
	length = end - begin + 2
	if length < minlength:
		(minlength, minbegin, minend) = (length, begin, end)
print(minlength)


def valid_substring(sub_s_counts, min_counts):
	for c in min_counts:
		if sub_s_counts[c] < min_counts[c]:
			return False
	return True

def get_data(n, s):
	quarter = n // 4
	counts = {'A': 0, 'C': 0, 'T': 0, 'G': 0}
	for i in range(len(s)):
		c = s[i]
		counts[c] += 1
	to_rem = {}
	to_add = {}
	for c in counts:
		value = quarter - counts[c]
		if value < 0:
			to_rem[c] = -value
		elif value > 0:
			to_add[c] = value
	return (to_add, to_rem)
n = int(input())
s = input()
(to_add, to_rem) = get_data(n, s)
min_result = sum([to_add[key] for key in to_add])
if len(to_rem) == 0:
	print(min_result)
else:
	result = n
	head = 0
	tail = 0
	sub_s_counts = {'A': 0, 'C': 0, 'T': 0, 'G': 0}
	for head in range(n):
		while not valid_substring(sub_s_counts, to_rem) and tail < n:
			sub_s_counts[s[tail]] += 1
			tail += 1
		if not valid_substring(sub_s_counts, to_rem) or head > tail:
			break
		length = tail - head
		if length < result:
			result = length
		sub_s_counts[s[head]] -= 1
	print(max(min_result, result))


def min_gene_modification(gene):
	n = len(gene)
	n_per_char = n // 4
	chars = 'ACGT'
	prefix_counters = {char: (n + 1) * [0] for char in chars}
	chars_to_reduce = {}
	min_slice_size = 0
	for char in chars:
		counter = fill_prefix_counter(gene, prefix_counters, char)
		if counter > n_per_char:
			n_to_reduce = counter - n_per_char
			chars_to_reduce[char] = n_to_reduce
			min_slice_size += n_to_reduce
	(left, right) = (0, min_slice_size - 1)
	composition = slice_composition(left, right, prefix_counters, chars_to_reduce)
	min_hit = len(gene) + 1
	while right != n - 1:
		left = reduce_left_side(gene, left, right, composition, chars_to_reduce)
		if hit(composition, chars_to_reduce) and min_hit > right - left:
			min_hit = right - left + 1
		right = extend_right_side(gene, right, composition)
	right = reduce_right_side(gene, left, right, composition, chars_to_reduce)
	if hit(composition, chars_to_reduce) and min_hit > right - left:
		min_hit = right - left + 1
	return min_hit

def reduce_left_side(gene, left, right, composition, chars_to_reduce):
	while left <= right:
		most_left_char = gene[left]
		if most_left_char in chars_to_reduce and composition[most_left_char] - chars_to_reduce[most_left_char] > 0:
			left += 1
			composition[most_left_char] -= 1
		elif most_left_char not in chars_to_reduce:
			left += 1
		else:
			break
	return left

def hit(composition, chars_to_reduce):
	return all((composition[char] >= v for (char, v) in chars_to_reduce.items()))

def extend_right_side(gene, right, composition):
	next_right_char = gene[right + 1]
	if next_right_char in composition:
		composition[next_right_char] += 1
	return right + 1

def reduce_right_side(gene, left, right, composition, chars_to_reduce):
	while left <= right:
		most_right_char = gene[right]
		if most_right_char in chars_to_reduce and composition[most_right_char] - chars_to_reduce[most_right_char] > 0:
			right -= 1
			composition[most_right_char] -= 1
		elif most_right_char not in chars_to_reduce:
			right -= 1
		else:
			break
	return right

def slice_composition(start, end, prefix_counters, chars_to_reduce):
	pc = prefix_counters
	composition = {}
	for (char, counter) in chars_to_reduce.items():
		composition[char] = pc[char][end] - pc[char][start - 1]
	return composition

def fill_prefix_counter(gene, prefix_counters, char_to_count):
	counter = 0
	for (i, char) in enumerate(gene):
		if char == char_to_count:
			counter += 1
		prefix_counters[char_to_count][i] = counter
	return counter
gene_len = int(input().strip())
gene = input().strip()
result = min_gene_modification(gene)
print(result)


import collections

def solve(n, string):
	extra_counts = collections.Counter(string) - collections.Counter('ATGC' * (n // 4))
	if not extra_counts:
		return 0
	current = collections.Counter()
	best = n
	start = 0
	for (end, c) in enumerate(string, 1):
		assert start <= end, (start, end)
		current[c] += 1
		if current[c] > extra_counts[c] and string[start] == c:
			char = string[start]
			while current[char] > extra_counts[char]:
				current[char] -= 1
				start += 1
				char = string[start]
			if all((current[key] >= required for (key, required) in extra_counts.items())):
				best = min(best, end - start)
	return best
print(solve(n=int(input()), string=input()))


N = int(input().strip())
gene = input().strip()

def check_gene(string):
	letters = [-N / 4, -N / 4, -N / 4, -N / 4]
	for char in gene:
		if char == 'A':
			letters[0] += 1
		elif char == 'T':
			letters[1] += 1
		elif char == 'C':
			letters[2] += 1
		elif char == 'G':
			letters[3] += 1
		else:
			pass
	if letters[0] == 0 and letters[1] == 0 and (letters[2] == 0) and (letters[3] == 0):
		return 0
	final_length = None
	head = 0
	tail = 0
	while head < len(string):
		if string[head] == 'A':
			letters[0] -= 1
		elif string[head] == 'T':
			letters[1] -= 1
		elif string[head] == 'C':
			letters[2] -= 1
		elif string[head] == 'G':
			letters[3] -= 1
		else:
			pass
		while letters[0] <= 0 and letters[1] <= 0 and (letters[2] <= 0) and (letters[3] <= 0) and (tail < head):
			temp_length = head - tail + 1
			if final_length == None:
				final_length = temp_length
			if temp_length < final_length:
				final_length = temp_length
			if string[tail] == 'A':
				letters[0] += 1
			elif string[tail] == 'T':
				letters[1] += 1
			elif string[tail] == 'C':
				letters[2] += 1
			elif string[tail] == 'G':
				letters[3] += 1
			else:
				pass
			tail += 1
		head += 1
	return final_length
print(check_gene(gene))


def is_valid(a, t):
	return a[0] <= t and a[1] <= t and (a[2] <= t) and (a[3] <= t)
N = int(input().strip())
(mx, ans) = (0, 999999)
G = ['A', 'C', 'G', 'T']
A = [0, 0, 0, 0]
S = input().strip()
target = N // 4
for i in range(N - 1, -1, -1):
	A[G.index(S[i])] += 1
	if not is_valid(A, target):
		mx = i + 1
		A[G.index(S[i])] -= 1
		break
for mn in range(-1, N - 1):
	if mn >= N - 1 or mx >= N or mn >= mx:
		break
	while not is_valid(A, target) and mx < N:
		A[G.index(S[mx])] -= 1
		mx += 1
	if mx > N or not is_valid(A, target):
		break
	subSingLength = max(0, mx - mn - 1)
	if subSingLength < ans:
		ans = subSingLength
	A[G.index(S[mn + 1])] += 1
print(ans)


import sys
from operator import sub
n = int(input().strip())
s = input().strip()
F = dict(((c, 0) for c in 'ACTG'))
for c in s:
	F[c] += 1
m = n // 4
needed = {}
for c in 'ACTG':
	if F[c] > m:
		needed[c] = F[c] - m
needed_keys = needed.keys()
if len(needed_keys) == 0:
	print(0)
	sys.exit(0)
answer = n
current = []
have = dict.fromkeys(needed_keys, 0)
for i in range(n):
	c = s[i]
	if c in needed_keys:
		current.append((i, c))
		have[c] += 1
		while len(current) > 1:
			c0 = current[0][1]
			if have[c0] > needed[c0]:
				current.pop(0)
				have[c0] -= 1
			else:
				break
		if all(map(lambda c: have[c] >= needed[c], needed_keys)):
			answer = min(answer, i - current[0][0] + 1)
print(answer)


from collections import Counter

def bear_steady_gene():
	len_gene = int(input())
	gene = input()
	gene_ctr = Counter(gene)
	if is_steady(gene, gene_ctr):
		print(0)
	else:
		result = float('inf')
		out = 0
		for num in range(len_gene):
			gene_ctr[gene[num]] -= 1
			while is_steady(gene, gene_ctr) and out <= num:
				result = min(result, num - out + 1)
				gene_ctr[gene[out]] += 1
				out += 1
		print(result)

def is_steady(gene, gene_ctr):
	return True if all((t <= len(gene) / 4 for t in gene_ctr.values())) else False
bear_steady_gene()


import sys

def solve(s, debug=0):

	def ge(c1, c2):
		for c in c1:
			if c1[c] < c2[c]:
				return False
		return True

	def le(c1, c2):
		for c in c1:
			if c1[c] < c2[c]:
				return True
		return False

	def equal(c1, c2):
		for c in c1:
			if c1[c] != c2[c]:
				return False
		return True

	def create_cache():
		chrs = 'ACGT'
		cache = {c: i for (i, c) in enumerate(chrs)}
		counts = [0] * 4
		for l in s:
			counts[cache[l]] += 1
		print(counts, file=sys.stderr)
		for c in cache:
			cache[c] = counts[cache[c]] - len(s) // 4
			if cache[c] < 0:
				cache[c] = 0
		cache = {u: v for (u, v) in cache.items() if v > 0}
		return cache

	def add(cache, c):
		if c in cache:
			cache[c] += 1

	def remove(cache, c):
		if c in cache:
			cache[c] -= 1
	cache = create_cache()
	print(cache, file=sys.stderr)
	if sum([cache[c] for c in cache]) == 0:
		return 0
	(fr, to) = (0, 0)
	new_cache = {c: 0 for c in cache}
	min_len = len(s)
	while fr != len(s):
		while to != len(s):
			add(new_cache, s[to])
			to += 1
			if ge(new_cache, cache):
				min_len = min(min_len, to - fr)
				if debug > 0:
					print('>=', fr, to, new_cache, min_len, file=sys.stderr)
				elif debug > 1:
					print('>=', fr, to, s[fr:to], new_cache, min_len, file=sys.stderr)
				break
		while fr != to:
			remove(new_cache, s[fr])
			fr += 1
			if ge(new_cache, cache):
				min_len = min(min_len, to - fr)
				if debug > 0:
					print('>=', fr, to, new_cache, min_len, file=sys.stderr)
				elif debug > 1:
					print('>=', fr, to, s[fr:to], new_cache, min_len, file=sys.stderr)
			elif le(new_cache, cache):
				break
	return min_len

def run():
	_ = input()
	s = input()
	print(solve(s, 1))
run()


N = int(input())
S = input().strip()
stable_n = N / 4
counts = {'A': 0, 'C': 0, 'T': 0, 'G': 0}
for c in S:
	counts[c] += 1
miss = {}
for (c, count) in counts.items():
	d = int(stable_n) - count
	if d < 0:
		miss[c] = abs(int(stable_n) - count)
	else:
		miss[c] = 0
miss_vector = (miss['A'], miss['C'], miss['T'], miss['G'])
best_length = N
min_length = abs(sum(miss_vector))
index = {'A': 0, 'C': 1, 'T': 2, 'G': 3}
v = [0, 0, 0, 0]
L = 0
R = min_length - 1
for x in range(min_length):
	v[index[S[x]]] += 1

def match(v1, v2):
	for x in range(len(v1)):
		if v1[x] < v2[x]:
			return False
	return True
while R < N:
	w = tuple(v)
	while L <= R and sum(w) >= min_length and match(w, miss_vector):
		if L == R:
			best_length = 0
		best_length = min(best_length, R - L + 1)
		v[index[S[L]]] -= 1
		L += 1
		w = tuple(v)
	R += 1
	if R < N:
		v[index[S[R]]] += 1
print(best_length)


n = int(input())
s = input()
stable_count = n // 4
r = {'A': 0, 'C': 0, 'T': 0, 'G': 0}
b = {'A': [0] * (n + 1), 'C': [0] * (n + 1), 'G': [0] * (n + 1), 'T': [0] * (n + 1)}
for i in range(1, n + 1):
	for c in b:
		b[c][i] = b[c][i - 1] + 1 if s[i - 1] == c else b[c][i - 1]
count = 0
for c in b:
	r[c] = b[c][n] - stable_count
	if r[c] > 0:
		count += r[c]
m = n
lastIndex = 0
for i in range(count, n + 1):
	if m == count:
		break
	found = True
	for c in b:
		if b[c][i] - b[c][lastIndex] < r[c]:
			found = False
			break
	if found:
		for j in range(lastIndex + 1, i - count + 1):
			update = True
			for c in b:
				if b[c][i] - b[c][j] < r[c]:
					update = False
					break
			if update:
				m = min(m, i - j)
				lastIndex = j
			else:
				break
		m = min(m, i - lastIndex)
print(m)


n = int(input().strip())
L = 'ACGT'
A = [[0] * (n + 1), [0] * (n + 1), [0] * (n + 1), [0] * (n + 1)]
for (i, c) in enumerate(input().strip()):
	for (j, l) in enumerate(L):
		A[j][i + 1] = A[j][i] + 1 if c == l else A[j][i]
req = [A[j][n] - n // 4 for j in range(len(L))]
if all((x == 0 for x in req)):
	print(0)
else:
	a = 0
	b = 1
	minlen = n
	while b < n + 1:
		if all((A[j][b] - A[j][a] >= req[j] for j in range(len(L)))):
			minlen = min(minlen, b - a)
			a += 1
		else:
			b += 1
	print(minlen)


_ = input()
s = input()
m = len(s) // 4
z = {c: max(0, s.count(c) - m) for c in 'ACGT'}

def comp(x):
	u = 0
	for y in z:
		if z[y] == 0:
			continue
		if z[y] > x[y]:
			return -1
		if z[y] < x[y]:
			u = 1
	return u
x = {'A': 0, 'C': 0, 'G': 0, 'T': 0}
best = len(s)
(i, j) = (0, 0)
while j <= len(s):
	c = comp(x)
	if c >= 0 and best > j - i:
		best = j - i
	if c < 0:
		if j == len(s):
			break
		x[s[j]] += 1
		j += 1
	elif i < j:
		x[s[i]] -= 1
		i += 1
	else:
		best = 0
		break
print(best)


def l2i(letter):
	return ['A', 'C', 'T', 'G'].index(letter)
n = int(input().strip())
s = input().strip()
globalCounts = [0, 0, 0, 0]
for letter in s:
	globalCounts[l2i(letter)] += 1
if all([c == globalCounts[0] for c in globalCounts]):
	print(0)
else:
	countsToFind = [max(0, ct - int(n / 4)) for ct in globalCounts]
	shortestLen = n
	start = 0
	end = 0
	currCounts = [0, 0, 0, 0]

	def okay():
		return all([currCounts[i] >= countsToFind[i] for i in range(4)])
	while end < n:
		while not okay():
			currCounts[l2i(s[end])] += 1
			end += 1
			if end >= n:
				break
		while okay():
			shortestLen = min(shortestLen, end - start)
			currCounts[l2i(s[start])] -= 1
			start += 1
	print(shortestLen)


def index_for(letter):
	return 'ATCG'.index(letter)

def frequencies(gene):
	return [gene.count('A'), gene.count('T'), gene.count('C'), gene.count('G')]

def add_to_frequencies(frequency_table, character):
	frequency_table[index_for(character)] += 1

def remove_from_frequencies(frequency_table, character):
	frequency_table[index_for(character)] -= 1

def suffices(frequency_table, requirements):
	for i in range(4):
		if requirements[i] > 0:
			if frequency_table[i] < requirements[i]:
				return False
	return True
length = int(input())
maximum = length // 4
gene = input()
total_frequencies = frequencies(gene)
excess = [0, 0, 0, 0]
for i in range(4):
	excess[i] = max(total_frequencies[i] - maximum, 0)
window_start = 0
window_end = 1
window_frequencies = frequencies(gene[0])
while not suffices(window_frequencies, excess):
	add_to_frequencies(window_frequencies, gene[window_end])
	window_end += 1
shortest_solution = window_end - window_start
for i in range(length - window_end - 1):
	while window_start < window_end and suffices(window_frequencies, excess):
		remove_from_frequencies(window_frequencies, gene[window_start])
		window_start += 1
		if suffices(window_frequencies, excess):
			shortest_solution = window_end - window_start
		else:
			window_start -= 1
			add_to_frequencies(window_frequencies, gene[window_start])
			break
	remove_from_frequencies(window_frequencies, gene[window_start])
	window_start += 1
	add_to_frequencies(window_frequencies, gene[window_end])
	window_end += 1
print(shortest_solution)


def chartoindex(char):
	if char == 'A':
		return 0
	elif char == 'T':
		return 1
	elif char == 'C':
		return 2
	else:
		return 3
n = int(input().strip())
start = input().strip()
diffAs = int(start.count('A') - n / 4)
diffTs = int(start.count('T') - n / 4)
diffCs = int(start.count('C') - n / 4)
diffGs = int(start.count('G') - n / 4)
easyout = max([abs(diffAs), abs(diffTs), abs(diffCs), abs(diffGs)])
if easyout == 0:
	print('0')
else:
	indices = [diffAs, diffTs, diffCs, diffGs]
	curcount = [0, 0, 0, 0]
	minlength = n
	leftindex = rightindex = 0
	while rightindex < n:
		curcount[chartoindex(start[rightindex])] += 1
		rightindex += 1
		while curcount[0] >= indices[0] and curcount[1] >= indices[1] and (curcount[2] >= indices[2]) and (curcount[3] >= indices[3]):
			if rightindex - leftindex < minlength:
				minlength = rightindex - leftindex
			curcount[chartoindex(start[leftindex])] -= 1
			leftindex += 1
	while curcount[0] >= indices[0] and curcount[1] >= indices[1] and (curcount[2] >= indices[2]) and (curcount[3] >= indices[3]):
		if rightindex - leftindex < minlength:
			minlength = rightindex - leftindex
		curcount[chartoindex(start[leftindex])] -= 1
		leftindex += 1
	print(minlength)


total_len = int(input())
sequence = input()
max_count = total_len // 4
lb = 0
rb = total_len

def is_valid(counts, more_counts={}):
	for k in counts:
		total = counts.get(k, 0) + more_counts.get(k, 0)
		if total > max_count:
			return False
	return True
left_counts = {}
right_counts = {}
while True:
	c = sequence[rb - 1]
	right_counts[c] = right_counts.get(c, 0) + 1
	if is_valid(right_counts):
		rb -= 1
	else:
		right_counts[c] -= 1
		break
while True:
	c = sequence[lb]
	left_counts[c] = left_counts.get(c, 0) + 1
	if is_valid(left_counts, right_counts):
		lb += 1
	else:
		left_counts[c] -= 1
		break
best = max(rb - lb, 0)
if best == 0:
	print(0)
	exit()
while rb < total_len:
	c = sequence[rb]
	rb += 1
	right_counts[c] -= 1
	while True:
		d = sequence[lb]
		left_counts[d] = left_counts.get(d, 0) + 1
		if is_valid(left_counts, right_counts):
			lb += 1
		else:
			left_counts[d] -= 1
			break
	len = rb - lb
	if len < best:
		best = len
print(best)


length = int(input())
dna = input()

def calculate_min_distance(stacks):
	min_index = -1
	max_index = 0
	for letter in stacks:
		stack = stacks[letter]
		if len(stack) > 0:
			index = stack[0]
			if min_index == -1 or index < min_index:
				min_index = index
		if len(stack) > 1:
			index = stack[-1]
			if index > max_index:
				max_index = index
	return max_index - min_index + 1

def stacks_full(stacks, diffs):
	for letter in stacks:
		stack = stacks[letter]
		if len(stack) != diffs[letter]:
			return False
	return True

def get_stable_dna(dna):
	balanced_count = int(len(dna) / 4)
	counts = {'A': [], 'T': [], 'C': [], 'G': []}
	for x in range(len(dna)):
		letter = dna[x]
		counts[letter].append(x)
	diffs = {}
	stacks = {}
	for key in counts:
		count = counts[key]
		diff = len(count) - balanced_count
		if diff > 0:
			diffs[key] = diff
			stacks[key] = []
	if len(diffs) == 0:
		return 0
	min_distance = len(dna)
	for x in range(len(dna)):
		letter = dna[x]
		if letter in stacks:
			stack = stacks[letter]
			stack.append(x)
			if len(stack) > diffs[letter]:
				stack.pop(0)
			if stacks_full(stacks, diffs):
				distance = calculate_min_distance(stacks)
				if distance < min_distance:
					min_distance = distance
	return min_distance
print(get_stable_dna(dna))


from collections import Counter
import sys
import math
n = int(input())
s1 = input()
s = Counter(s1)
if all((e <= n / 4 for e in s.values())):
	print(0)
	sys.exit(0)
result = float('inf')
out = 0
for mnum in range(n):
	s[s1[mnum]] -= 1
	while all((e <= n / 4 for e in s.values())) and out <= mnum:
		result = min(result, mnum - out + 1)
		s[s1[out]] += 1
		out += 1
print(result)