leetcode
leetcode 1151 ~ 1200
替换子串得到平衡字符串

替换子串得到平衡字符串

难度:

标签:

题目描述

代码结果

运行时间: 94 ms, 内存: 16.4 MB


/*
* 思路:
* 1. 统计每个字符的出现次数。
* 2. 计算每个字符超过n/4的部分,这些部分需要通过替换来平衡。
* 3. 使用滑动窗口技术找到最小的子串,使得替换这个子串后字符串平衡。
*/
import java.util.stream.IntStream;
public class BalancedStringStream {
    public int balancedString(String s) {
        int n = s.length();
        int k = n / 4;
        int[] count = new int[128];
        s.chars().forEach(c -> count[c]++);
        int[] minLen = { n };
        IntStream.range(0, n).forEach(i -> {
            count[s.charAt(i)]--;
            while (count['Q'] <= k && count['W'] <= k && count['E'] <= k && count['R'] <= k) {
                minLen[0] = Math.min(minLen[0], i - j + 1);
                count[s.charAt(j++)]++;
            }
        });
        return minLen[0];
    }
}

解释

方法:

本题解使用滑动窗口(sliding window)策略来找到使字符串平衡的最小子串长度。首先,计算每个字符'Q', 'W', 'E', 'R'的出现次数,并确定每个字符应有的平均出现次数(n/4)。接着,创建一个字典d来记录每个字符超出平均值的数量。若所有字符的数量都不超过平均值,则字符串已经平衡,直接返回0。使用双指针技术(左指针l和右指针r),扩展右指针以包含足够的超额字符,然后逐步移动左指针以缩小窗口,直到窗口内的字符不再能覆盖所有超额字符。过程中记录并更新最小窗口长度。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么在初始化字典d时,只记录了超过平均值的字符,而没有记录低于平均值的字符的信息?
在这个问题中,目的是找到最小的子串,使得整个字符串中每个字符的数量不超过平均值。记录超过平均值的字符是因为我们需要通过替换这些字符来减少它们的数量,从而达到平衡。低于平均值的字符不需要在这个过程中被减少,所以没有必要记录它们。关键在于缩减超额部分,而不是增加不足部分。
🦆
在滑动窗口中,当匹配到所有超额字符并尝试缩小窗口时,如果s[l]不在字典d中,是否应该移动左指针l,这样的操作对结果计算有何影响?
当s[l]不在字典d中,表示这个字符的数量不需要减少,因此移动左指针l来缩小窗口是适当的操作。这意味着我们可以尝试减小窗口的大小而不影响超额字符的匹配状态。这种操作有助于我们找到可能的最小窗口,因此是寻找最优解的重要步骤。
🦆
解题思路中提到使用双指针策略,但实际操作似乎更接近于滑动窗口方法。请问双指针和滑动窗口在概念上有何不同?
双指针策略通常涉及两个指针以不同的速度或方向在数组或列表上移动以解决问题,比如在排序数组中找到特定和的两个数字。而滑动窗口是双指针策略的一种,特别适用于需要在字符串或数组中查找符合某些条件的连续子区间的问题。在滑动窗口方法中,两个指针代表窗口的边界,共同向前移动以探索所有可能的窗口。尽管滑动窗口是基于双指针的,但它更侧重于窗口的大小和窗内元素的处理。

相关问题