LeetCode 1234. 替换子串得到平衡字符串

Categories:

题目描述
思路分析
1. 解法一：滑动窗口（推荐）
相似题目

题目描述

✅ 1234. 替换子串得到平衡字符串

思路分析

解法一：滑动窗口（推荐）

核心思路：

统计字符串中 Q/W/E/R 的总次数，目标是都不超过 n / 4。

用滑动窗口代表将被替换的子串，窗口外的字符计数需满足要求。

右指针扩展减少窗口外计数，满足条件后收缩左指针更新最小长度。

复杂度分析：

时间复杂度：O(n)，双指针一次遍历。

空间复杂度：O(1)，固定 4 种字符计数。

class Solution {
    public int balancedString(String s) {
        int n = s.length();
        int target = n / 4;
        int[] cnt = new int[128];
        for (int i = 0; i < n; i++) {
            cnt[s.charAt(i)]++;
        }

        if (cnt['Q'] <= target && cnt['W'] <= target && cnt['E'] <= target && cnt['R'] <= target) {
            return 0;
        }

        int ans = n;
        int left = 0;
        for (int right = 0; right < n; right++) {
            cnt[s.charAt(right)]--;

            while (left <= right
                    && cnt['Q'] <= target && cnt['W'] <= target
                    && cnt['E'] <= target && cnt['R'] <= target) {
                ans = Math.min(ans, right - left + 1);
                cnt[s.charAt(left)]++;
                left++;
            }
        }
        return ans;
    }
}

func balancedString(s string) int {
    n := len(s)
    target := n / 4
    cnt := make([]int, 128)
    for i := 0; i < n; i++ {
        cnt[s[i]]++
    }

    if cnt['Q'] <= target && cnt['W'] <= target && cnt['E'] <= target && cnt['R'] <= target {
        return 0
    }

    ans := n
    left := 0
    for right := 0; right < n; right++ {
        cnt[s[right]]--

        for left <= right && cnt['Q'] <= target && cnt['W'] <= target && cnt['E'] <= target && cnt['R'] <= target {
            if right-left+1 < ans {
                ans = right - left + 1
            }
            cnt[s[left]]++
            left++
        }
    }
    return ans
}

相似题目

题目	难度	考察点
76. 最小覆盖子串	困难	滑动窗口
424. 替换后的最长重复字符	中等	滑动窗口
438. 找到字符串中所有字母异位词	中等	滑动窗口
567. 字符串的排列	中等	滑动窗口
3. 无重复字符的最长子串	中等	滑动窗口

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/61216580