Replace the Substring for Balanced String
Medium · Sliding Window · String · Sliding Window
Problem
You are given a string s of length n made only of the letters 'Q', 'W', 'E' and 'R', where n is a multiple of 4. The string is balanced when each of the four letters appears exactly n / 4 times.
You may pick one contiguous substring of s and replace it with any string of the same length. Return the minimum length of such a substring that makes s balanced, or 0 if s is already balanced.
Examples
Input: s = "QQQW" Output: 2
Q appears 3 times but should appear once, so a substring holding two Qs, such as "QQ", must be replaced (for example by "ER").
Input: s = "QWER" Output: 0
Every letter appears exactly once.
Input: s = "QQQQ" Output: 3
Three of the four Qs have to become W, E and R.
Constraints
- 4 <= n <= 10^5
- n is a multiple of 4
- s contains only 'Q', 'W', 'E' and 'R'
Approaches
- Baseline: every start, grow until it works — time O(n²), space O(1)
Follow-up
The same window answers the question for any alphabet: with k letters and a target of n / k each, the check costs O(k) per step, or O(1) if you track how many letters are still over the limit. When you may delete the substring instead of replacing it, the target per letter becomes whatever cap you are given, and the window test is unchanged.
Related problems
Start free on Cariara · Coding problems · System design studio
