Open chencl1986 opened 1 month ago
原题链接: https://leetcode.cn/problems/replace-the-substring-for-balanced-string/
解题要点:
m
n / 4
s
left
right
right - left + 1
0
n - 1
s = "QQWQQEQR"
left = 4; right = 7
QEQR
解题思路:
map
QWER
left <= right
map[s[right]]
map[s[left++]]
/** * @param {string} s * @return {number} */ var balancedString = function(s) { // 实用map统计当前字符串s中各个字符的数量 let map = { 'Q': 0, 'W': 0, 'E': 0, 'R': 0, } // 统计各个字符的数量 for (const c of s) { map[c]++ } const n = s.length // 计算如果是平衡字符串,每个字符的数量 const target = n / 4 // 如果每个字符的数量都为n / 4,s为平衡字符串 if ( map.Q === target && map.W === target && map.E === target && map.R === target ) { return 0 } // 缓存结果,最大值为n - 1,初始值大于等于n - 1即可 let result = n - 1 // 实用两个指针,从字符串中截取一个范围 for (let left = 0, right = 0; right < n; right++) { // 每次滑入窗口一个字符,就将其数量减一 map[s[right]]-- // 字符串中除了窗口以外的部分,每个字符的数量都小等于target // 就意味着字符串能够通过变换right - left + 1个字符,成为“平衡字符串” while ( // 左指针必须小等于右指针,才能形成窗口 left <= right && // 查看窗口以外的字符,数量是否都小于target map.Q <= target && map.W <= target && map.E <= target && map.R <= target ) { // 在所有结果中取最小值 result = Math.min(result, right - left + 1) // 每次查找完之后,窗口要向右移动 // 同时会有一个字符被移出窗口,需要将它的数量加一 map[s[left++]]++ } } return result };
原题链接: https://leetcode.cn/problems/replace-the-substring-for-balanced-string/
解题要点:
m
,只要剩下的部分每个字符的数量都小于n / 4
,就表示s
能够通过替换m
个字符,变为“平衡字符串”left
和right
,将两者之间长度为right - left + 1
的字符串当做一个窗口,即可在s
中截取出长度为m
的字符串right
从0
开始一直移动到n - 1
位置,左边界left
跟随right
移动,查找合适的窗口s = "QQWQQEQR"
,窗口到最右侧时,left = 4; right = 7
,此时在窗口中的字符串为QEQR
,窗口即使继续向右移动,也无法满足上述条件,直接退出循环即可解题思路:
map
统计字符串s
中各个字符的数量QWER
中每个字符的数量都是n / 4
,表示s
就是“平衡字符串”left
和right
指针,right
从左向右移动,同时left <= right
right
向右移动一位,就将map[s[right]]
的数量减一,表示有字符移入窗口left
向左移动一位,就将map[s[left++]]
加一,表示有字符移出窗口map
中剩下的字符,就是窗口外的字符数量,因此只要判断QWER
的数量是否小等于n / 4
即可