# 1234. Replace the Substring for Balanced String

yPhantom 2019年10月20日 137次浏览

You are given a string containing only 4 kinds of characters `'Q',` `'W', 'E'` and `'R'`.

A string is said to be balanced if each of its characters appears `n/4` times where `n` is the length of the string.

Return the minimum length of the substring that can be replaced with any other string of the same length to make the original string `s` balanced.

Return 0 if the string is already balanced.

Example 1:

``````Input: s = "QWER"
Output: 0
``````

Example 2:

``````Input: s = "QQWE"
Output: 1
Explanation: We need to replace a 'Q' to 'R', so that "RQWE" (or "QRWE") is balanced.
``````

Example 3:

``````Input: s = "QQQW"
Output: 2
Explanation: We can replace the first "QQ" to "ER".
``````

Example 4:

``````Input: s = "QQQQ"
Output: 3
Explanation: We can replace the last 3 'Q' to make s = "QWER".
``````

Constraints:

• `1 <= s.length <= 10^5`
• `s.length` is a multiple of `4`
• `s`contains only `'Q'`, `'W'`, `'E'` and `'R'`.

## Solution

• 遍历整个字符串获取所有字符的出现次数
• 初始化话窗口，左右为left = 0, right = 0，窗口大小一开始为1
• 窗口每次向右移动时，进入窗口的对应字符频率减一，即count[right]--，同时窗口左边出去的字符的频率对应加一，即count[left++]++

``````class Solution {
public int balancedString(String s) {
int[] count = new int;
int n = s.length();
int left = 0;
int minWindowLen = n;

for (int i = 0; i < s.length(); i++) {
++count[s.charAt(i)];
}

for (int right = 0; right < n; right++) {
--count[s.charAt(right)];
// left小于n而不是right, 如果left小于等于right, minWindowLen最小值为1
while (left < n && count['Q'] <= n / 4 && count['W'] <= n / 4 && count['E'] <= n / 4 && count['R'] <= n / 4) {
minWindowLen = Math.min(minWindowLen, right - left + 1);
++count[s.charAt(left++)];
}
}
return minWindowLen;
}
}
``````