Replace the Substring for Balanced…

1. Define the problem

Replace the Substring for Balanced String

You are given a string s of length n containing only the characters 'Q', 'W', 'E', and 'R'. A string is balanced if each of the four characters appears exactly n / 4 times. Return the length of the shortest substring you can replace with any characters to make s balanced . Shrink a window from the left as long as every character left outside it still appears at most n / 4 times — that outside count is what the replacement has to fix.

Constraints

1 ≤ n ≤ 10⁵
n is a multiple of 4
s_i is 'Q', 'W', 'E', or 'R'

Example

Inputs = "QWER"

Output0

Explanation Every character already appears exactly n / 4 = 1 time, so s is already balanced.

2. Visualize the solution

Shrink while the outside counts stay balanced

Statusshrink

Removing s[0]=Q from outside leaves Q1,W1,E1,R0 — all within target; candidate length 1.

What happens in this step

s="QQWE", n=4, target = n/4 = 1
starting outside counts: Q=2, W=1, E=1, R=0 (not balanced yet)

right=0: remove s[0]='Q' from outside → Q=1, W=1, E=1, R=0
  every count <= target=1 → shrink is allowed
  candidate length = right - left + 1 = 0 - 0 + 1 = 1, best = 1
  add s[left]='Q' back outside (Q → 2), left advances to 1
  recheck: Q=2 > target → shrinking stops for this right

Step 1 of 4

Steps to visualize

Count how many times each of Q, W, E, R appears in the whole string.
If every count already equals n / 4, the string is balanced and the answer is 0.
Otherwise, grow right and remove that character from the outside counts.
While every outside count is at most n / 4, record the window length and shrink from the left, adding the character back outside.
The shortest recorded window is the answer.

3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Shrink while the outside counts stay balanced

Statusshrink

Removing s[0]=Q from outside leaves Q1,W1,E1,R0 — all within target; candidate length 1.

What happens in this step

s="QQWE", n=4, target = n/4 = 1
starting outside counts: Q=2, W=1, E=1, R=0 (not balanced yet)

right=0: remove s[0]='Q' from outside → Q=1, W=1, E=1, R=0
  every count <= target=1 → shrink is allowed
  candidate length = right - left + 1 = 0 - 0 + 1 = 1, best = 1
  add s[left]='Q' back outside (Q → 2), left advances to 1
  recheck: Q=2 > target → shrinking stops for this right

Step 1 of 4

4. Solution

Solution

solution.tsTypeScript

function balancedString(s) {
  const n = s.length;
  const target = n / 4;
  const count = { Q: 0, W: 0, E: 0, R: 0 };

  for (const c of s) count[c]++;

  if (count.Q === target && count.W === target && count.E === target && count.R === target) {
    return 0;
  }

  let left = 0;
  let best = n;

  for (let right = 0; right < n; right++) {
    count[s[right]]--;

    while (
      left < n &&
      count.Q <= target &&
      count.W <= target &&
      count.E <= target &&
      count.R <= target
    ) {
      best = Math.min(best, right - left + 1);
      count[s[left]]++;
      left++;
    }
  }

  return best;
}

Time: O(n)
Space: O(1)

5. Test cases

Test cases

Input	Expected	Covers
`s = "QWER"`	`0`	Docstring example — already balanced
`s = "QQWE"`	`1`	One extra Q needs a single-character replacement
`s = "QQQW"`	`2`	Two extra Qs need a length-2 replacement
`s = "WWQR"`	`1`	Same imbalance pattern with a different letter
`s = "QQQQ"`	`3`	Only one letter present — most of the string must be replaced
`s = "QQWWEERR"`	`0`	Already balanced at a longer length
`s = "QQQQWWER"`	`2`	Mixed imbalance across all four letters

Replace the Substring for Balanced String