You are viewing a single comment's thread. Return to all comments →
python3 working solution
def steadyGene(gene): n = len(gene) gene_map = collections.Counter(gene) extra = "" for key, val in gene_map.items(): if val > n//4: extra += key*(val-n//4) m = len(extra) if m == 0: return 0 extra_map = collections.Counter(extra) i, j, count, ans, temp_map = 0, 0, 0, n, {} def add_to_temp(count): temp_map[gene[j]] = temp_map.get(gene[j], 0) + 1 if temp_map.get(gene[j]) <= extra_map.get(gene[j], 0): count += 1 return temp_map, count, j+1 while j < n: if count < m: temp_map, count, j = add_to_temp(count) else: ans = min(ans, j-i) if temp_map.get(gene[i], 0)-1 >= extra_map.get(gene[i], -1): temp_map[gene[i]] -= 1 i += 1 else: temp_map, count, j = add_to_temp(count) return ans
Key concept is: Minimum Window Substring
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 →
python3 working solution
Key concept is: Minimum Window Substring