You are viewing a single comment's thread. Return to all comments →
def steadyGene(chars: list[str]) -> int: from collections import defaultdict, deque char_to_cnt = defaultdict(lambda: 0) for char in chars: char_to_cnt[char] += 1 char_to_surplus = defaultdict(lambda: 0) for char in ['A', 'C', 'T', 'G']: surplus = char_to_cnt[char] - len(chars) // 4 if surplus > 0: char_to_surplus[char] = surplus if not char_to_surplus: return 0 lo = hi = 0 lohi_to_cnt = defaultdict(lambda: 0) lohi_to_cnt[chars[lo]] = 1 def is_satisfying() -> bool: for char, surplus in char_to_surplus.items(): if lohi_to_cnt[char] < surplus: return False return True candidates = [] while True: if is_satisfying(): candidates.append(hi - lo + 1) hi += 1 if hi == len(chars): break lohi_to_cnt[chars[hi]] += 1 while lohi_to_cnt[chars[lo]] > char_to_surplus[chars[lo]]: lohi_to_cnt[chars[lo]] -= 1 lo += 1 return min(candidates)
Seems like cookies are disabled on this browser, please enable them to open this website
Bear and Steady Gene
You are viewing a single comment's thread. Return to all comments →