Shortest Substring to Rewrite for a Balanced Gene String

Reported in interviews at Citadel

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$, n divisible by 4, all characters in {A, C, G, T}.

Examples:

  • s = "GAAA" with n = 4 and n/4 = 1: A appears 3 times, so you must rewrite a window covering 2 of the 3 As; the answer is 2.
  • s = "ACGT" (n = 4) is already balanced, so the answer is 0.
  • s = "AACGAATG" has n = 8 and n/4 = 2: A appears 4 times (two over the target of 2); the shortest window whose removal leaves every outside count at most 2 has length 2, so the answer is 2.
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.

Related free problems