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
Explanation: s is already balanced.

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
  • scontains 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[128];
        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;
    }
}

类似题目:

参考: