My initial solution of simply searching through from the minimum possible length to the three-quarters of the length of gene (the maximum possible length of a sub-string requiring replace which would occur all the letters where the same; like a string of all 'A's) did not work; it was too slow for the later tests cases. It seems that other people have created sufficiently performant solutions using this approach in C++ but, I couldn't get it to work in Python. So, I binary-searched for the answer instead

`def works (o, L, l, dd): c = { 'A': 0, 'C': 0, 'G': 0, 'T': 0, }

c['A'] = o['A']
c['C'] = o['C']
c['G'] = o['G']
c['T'] = o['T']

i = 0 
while i < L - l:
    if c['A'] >= dd['A'] and c['C'] >= dd['C'] and c['G'] >= dd['G'] and c['T'] >= dd['T']:
        return True

    c[gene[i]] -= 1
    c[gene[i+l]] += 1
    i += 1

return False

def steadyGene(gene): L = len(gene) d = { 'A': 0, 'C': 0, 'G': 0, 'T': 0 }

for g in gene:
    d[g] += 1

dd = {
    'A': 0,
    'C': 0,
    'G': 0,
    'T': 0
}

ml = 0
for c, v in d.items():
    ddd = max(0, v - L // 4)
    dd[c] = ddd
    ml += ddd 

low, high = ml, 3*L//4 
while low < high:
    mid = (low + high) // 2

    o = {
        'A': 0,
        'C': 0,
        'G': 0,
        'T': 0
    }

    for s in range(0, mid):
        o[gene[s]] += 1

    if works(o, L, mid, dd):
        high = mid
    else:
        low = mid + 1

return low`