【leetcode】1234. Replace the Substring for Balanced String

题目如下：

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

s contains only 'Q', 'W', 'E' and 'R'.

解题思路：如果字符串需要替换后才能到达平衡，那么说明至少有一个字符出现的次数超过1/4，当然至多也只有三个字符出现的次数都超过1/4。假设x1...xn为超过1/4的字符，那么就需要将xn们替换成不超过1/4的字符，具体每个xn需要替换的次数为 xn出现的次数 - len(s)/4，记为dn。所以题目就转换成找出一个最短的字符串，使得至少要包含dn的xn。如下图，输入为：WQWRQQQW，很容易可以求出每个字符在[0~i]区间内出现的个数，假设符合题目要求的子字符串是从下标i开始，只需要找出Q[i] + dn出现的下标j，即表示在i~j区间内Q出现的个数满足最小需要删除的个数，因为Q在区间内出现的次数有序，这里可以用二分查找，同时求出其他超过1/4的字符对应出现的下标，并求出这些下标的最大值，这个最大值就是子字符串是从下标i开始满足题目要求的子字符串最小的长度，遍历整个输入，求出[0~len(s)]区间内最小的长度即可。

代码如下：

class Solution(object):

    def balancedString(self, s):

        """

        :type s: str

        :rtype: int

        """

        dic = {'Q':{},'W':{},'E':{},'R':{}}

        char = ['Q','W','E','R']

        char_count = [0,0,0,0]

        s = s.replace('\n','')

        for i in range(len(s)):

            inx = char.index(s[i])

            char_count[inx] += 1

            dic[s[i]][char_count[inx]] = i

        res = float('inf')

        char_count_2 = [0, 0, 0, 0]

        for i in range(len(s)):

            inx = char.index(s[i])

            if char_count[inx] <= len(s)/4:

                continue

            count = -float('inf')

            for j in range(len(char)):

                if char_count[j] <= len(s)/4:

                    continue

                diff = char_count[j] - len(s)/4

                if char_count_2[j] + diff in dic[char[j]]:

                    end = dic[char[j]][char_count_2[j] + diff]

                    count = max(count, end - i +1)

                else:

                    count = -float('inf')

                    break

            if count != -float('inf'):

                res = min(res,count)

            char_count_2[inx] += 1

        return res if res != float('inf') else 0

秒客网

【leetcode】1234. Replace the Substring for Balanced String

相关文章