Shortest Substring to Rewrite for a Balanced Gene String
Problem statement
You are given a string s over the alphabet {A, C, G, T} whose length n is a multiple of 4. The string is balanced when each of A, C, G, T appears exactly n/4 times. In one operation you may pick a single contiguous substring of s and overwrite each of its characters with any letters from {A, C, G, T} you choose. Return the minimum length of a substring you must rewrite so that s becomes balanced. If s is already balanced, the answer is 0.
Complete:
def balancedString(s: str) -> int:
Constraints:
- $4 \le n \le 10^5$,
ndivisible by4, all characters in{A, C, G, T}.
Examples:
s = "GAAA"withn = 4andn/4 = 1:Aappears 3 times, so you must rewrite a window covering 2 of the 3As; the answer is2.s = "ACGT"(n = 4) is already balanced, so the answer is0.s = "AACGAATG"hasn = 8andn/4 = 2:Aappears 4 times (two over the target of 2); the shortest window whose removal leaves every outside count at most 2 has length2, so the answer is2.
Show hint
Since you may write anything inside the chosen substring, what constraint do the characters you leave untouched have to satisfy?
Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.