LeetCode 1156. 单字符重复子串的最大长度

约 6 分钟
文章信息 8 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节 微软 快手
标签
字符串 哈希表 滑动窗口

题目描述

✅ 1156. 单字符重复子串的最大长度

image-20260928230114016

image-20260928230114019

题意分析

可以在字符串中任选两个位置交换一次，也可以不交换。求操作后能够得到的最长连续同字符子串长度，子串中的每个字符都必须相同。

交换只改变位置，不会增加某种字符的总数量。因此即使某段只差一个字符就能连成更长的一段，也要确认整个字符串中有足够多的目标字符。

解法：枚举目标字符的滑动窗口

核心思路

[!blue]

固定最终子串使用的目标字母。一次交换最多从区间外换入一个目标字符，因此最终能变成全目标字符的区间，在交换前至多包含一个非目标字符。用滑动窗口维护这个限制，就能枚举可能的区间，而不必枚举两个交换位置。

先统计目标字母在全串的次数 freq[target]。扫描时用 diff 记录窗口内非目标字符数，加入右端后若 diff > 1，就持续移动左端，直到重新只剩至多一个异类。

对一个长度为 len 的合法窗口，如果没有异类，它已经是一段同字符子串。如果有一个异类且 len <= freq[target]，窗口内只有 len - 1 个目标字符，全局数量又至少为 len，说明窗口外一定还有一个，可以交换进来，形成长度为 len 的连续段。

若窗口长度超过全局次数，因为异类至多一个，只可能有 len = freq[target] + 1。这时不能得到整个窗口长度，但一定能得到少一格的长度：异类在端点时直接舍去该端点；异类在内部时，把它与窗口端点的一个目标字符交换，再舍去成为异类的端点。剩余部分连续且全部为目标字符。

所以每个合法窗口能够贡献的长度恰好为 min(len, freq[target])。固定右端点时，更长合法窗口的这个值不会更小，因此保留滑动窗口中最长的合法范围即可。对出现过的每种字母分别扫描，再取最大值，就覆盖了所有可能的目标字符与区间。

解题步骤

  1. 统计每个小写字母在整串中的出现次数。
  2. 枚举出现过的目标字母，初始化左端点和窗口异类数 diff = 0。
  3. 向右扩展窗口，右端不是目标字母就令 diff++。
  4. 异类超过一个时缩小左端；移出异类时减少 diff，直到窗口重新合法。
  5. 用窗口长度与目标总次数的较小值更新答案，完成所有目标字母的扫描后返回最大长度。

代码实现

class Solution {
    public int maxRepOpt1(String text) {
        int[] freq = new int[26];

        for (int i = 0; i < text.length(); i++) {
            freq[text.charAt(i) - 'a']++;
        }

        int ans = 0;

        for (int target = 0; target < 26; target++) {
            if (freq[target] == 0) {
                continue;
            }

            int left = 0;
            int diff = 0;

            for (int right = 0; right < text.length(); right++) {
                if (text.charAt(right) - 'a' != target) {
                    diff++;
                }

                // 一次交换最多补一个异类位置，超过时收缩。
                while (diff > 1) {
                    if (text.charAt(left) - 'a' != target) {
                        diff--;
                    }

                    left++;
                }

                int len = right - left + 1;

                // 交换不创造字符，实际长度不能超过全局数量。
                ans = Math.max(ans, Math.min(len, freq[target]));
            }
        }

        return ans;
    }
}

func maxRepOpt1(text string) int {
    freq := make([]int, 26)
    for i := 0; i < len(text); i++ {
        freq[text[i]-'a']++
    }

    ans := 0
    for target := 0; target < 26; target++ {
        if freq[target] == 0 {
            continue
        }

        left := 0
        diff := 0
        for right := 0; right < len(text); right++ {
            if int(text[right]-'a') != target {
                diff++
            }

            // 一次交换最多补一个异类位置，超过时收缩。
            for diff > 1 {
                if int(text[left]-'a') != target {
                    diff--
                }
                left++
            }

            length := right - left + 1
            // 交换不创造字符，实际长度不能超过全局数量。
            if length > freq[target] {
                length = freq[target]
            }
            if length > ans {
                ans = length
            }
        }
    }

    return ans
}

复杂度分析

  • 时间复杂度：$O(26n)$，每个目标字母的左右指针都只单向移动，固定小写字母表下为 $O(n)$。
  • 空间复杂度：$O(1)$，仅保存 26 个频次和固定数量的窗口变量。

关键点总结

[!green]

  • 窗口的异类数量限制一次交换能修复几个位置，全局频次限制实际有多少目标字符可用。
  • 频次封顶后的长度有明确构造方式，即使没有窗口外字符可换入，也能通过端点处理达到。
  • 每个最终答案都有一种目标字母，逐字母扫描能够完整覆盖候选。

易错点总结

[!yellow]

  • 只维护一个异类却不按全局次数封顶，会虚构字符串中不存在的额外目标字符。
  • 允许两个异类留在窗口，一次交换无法把两处都变成目标字符。
  • 把操作当作任意替换，会忽略交换前后字符总量不变的约束。
  • 缩左时只有移出异类才移动指针，会卡在窗口开头的目标字符上；每次都应移动左端。
  • 不允许零次交换，会错误处理原本已经全部相同的输入。

相似题目

题目 难度 关联与区别
424. 替换后的最长重复字符 中等 原题可直接替换字符，本题只能交换已有字符，合并重复段的长度还受全局字符总次数限制。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/69013885
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！