import java.io.*;

class Result {

/*
 * Complete the 'steadyGene' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts STRING gene as parameter.
 */

public static int steadyGene(String gene) {
    int n = gene.length();
    int target = n / 4;
    int[] count = new int[128];

    for (char c : gene.toCharArray()) {
        count[c]++;
    }

    // If already steady
    if (count['A'] == target && count['C'] == target && count['G'] == target && count['T'] == target) {
        return 0;
    }

    int minLen = n;
    int left = 0;

    for (int right = 0; right < n; right++) {
        count[gene.charAt(right)]--;

        while (count['A'] <= target && count['C'] <= target && count['G'] <= target && count['T'] <= target) {
            minLen = Math.min(minLen, right - left + 1);
            count[gene.charAt(left)]++;
            left++;
        }
    }

    return minLen;
}

}

public class Solution { public static void main(String[] args) throws IOException { BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    int n = Integer.parseInt(bufferedReader.readLine().trim());
    String gene = bufferedReader.readLine();

    int result = Result.steadyGene(gene);

    bufferedWriter.write(String.valueOf(result));
    bufferedWriter.newLine();

    bufferedReader.close();
    bufferedWriter.close();
}

}

Lmao I was pulling out my hair due to a runtime error, turns out it was just my debug print statements being waayyyy too big given the input size lol

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`

If you imagine us initially having every character in the gene, we can 'reverse' the problem to try and remove the fewest characters possible, while still having the other characters be below the required limit of . This transforms the problem into a classic sliding window, where we need to find the smallest window to 'remove', such that the characters outside of the window are still valid.

def steadyGene(gene):
    N = len(gene)
    goal = N // 4
    curr = Counter(gene)
    ans = N
    l = 0
    for r in range(N):
        curr[gene[r]] -= 1
        while l < N and max(curr.values()) <= goal:
            ans = min(ans, r - l + 1)
            curr[gene[l]] += 1
            l += 1
    return ans

include

using namespace std;

int test(int n, string s) { int required_count = n / 4; map mp; for (char it : s) { mp[it]++; } bool ok = true; for (auto tam : mp) { if (tam.second > required_count) { ok = false; break; } } if (ok) return 0; int min_val = n; int start = 0; for (int end = 0; end < n; end++) { mp[s[end]]--; while (mp['A'] <= required_count && mp['C'] <= required_count && mp['G'] <= required_count && mp['T'] <= required_count) { min_val = min(min_val, end - start + 1); mp[s[start]]++; start++; } } return min_val; }

int main() { int n; cin >> n; string s; cin >> s; cout << test(n, s) << endl; return 0; }