LeetCode 466. 统计重复个数

约 6 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 困难 未解决 1-2 字节
标签
字符串 动态规划 双指针

题目描述

✅ 466. 统计重复个数

image-20260929100719585

image-20260929100719695

题意分析

源字符串是 s1 连续重复 n1 次，目标的一组是 s2 连续重复 n2 次。允许从源字符串中删除字符，求最多能按顺序得到多少组完整目标；匹配的是子序列，字符不要求连续。

解法：循环节检测

核心思路

[!blue]

先不考虑 n2，连续匹配尽可能多份 s2。用 index 表示下一次等待匹配的 s2 下标，遇到所需字符就立刻匹配；走完一份 s2 后令 index = 0，完整匹配数 matched 加一。选择最早能匹配的位置不会减少后续可用空间，所以这种贪心能得到最多的完整份数。

不实际展开重复字符串，而是逐份扫描 s1，用 rounds 记录已处理份数。每份 s1 都相同，因此在块边界上，从同一个 index 出发，之后的匹配过程和新增份数也完全相同；不断增长的 matched 不会影响下一步行为，状态只需 index。

用 seen[index] 保存首次到达这个状态时的 (rounds, matched)。再次遇到时，两次记录之差给出循环节：cycleRounds 份 s1 能增加 cycleMatches 份 s2，并回到相同 index。剩余源串中还能容纳多少个完整循环，就同时增加对应的 rounds 和 matched，index 保持不变。

跳过后剩余不足一个循环节，继续逐份扫描即可。代码用 accelerated 保证只做一次批量跳跃。即使循环产出为 0，也可以照常跳过，因为跳跃次数只取决于消耗多少份 s1。最终将完整 s2 份数除以 n2，舍去不足一组的部分。

解题步骤

  1. 初始化 index = 0、rounds = 0、matched = 0，记录初始快照 seen[0] = (0, 0)。
  2. 扫描一份 s1，逐字符推进 index，每匹配完整一份 s2 就重置下标并增加 matched；随后令 rounds++。
  3. 未加速且当前 index 首次出现时，保存快照；再次出现时，计算两次快照的轮数差和匹配数差。
  4. 计算 cycles = (n1 - rounds) / cycleRounds，同时跳过对应源串份数并累加匹配产出，然后将 accelerated 置为 true。
  5. 扫描剩余源串，返回 matched / n2。

代码实现

class Solution {
    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
        Map<Integer, long[]> seen = new HashMap<>();

        seen.put(0, new long[] {
            0,
            0
        });

        int index = 0;
        int rounds = 0;
        long matched = 0;
        boolean accelerated = false;

        while (rounds < n1) {
            for (int i = 0; i < s1.length(); i++) {
                if (s1.charAt(i) == s2.charAt(index)) {
                    index++;

                    if (index == s2.length()) {
                        index = 0;
                        matched++;
                    }
                }
            }

            rounds++;

            if (!accelerated) {
                long[] previous = seen.get(index);

                if (previous == null) {
                    seen.put(index, new long[] {
                        rounds,
                        matched
                    });
                } else {
                    // 相同匹配下标之间的轮数差和产出差构成一个循环节。
                    int cycleRounds = rounds - (int) previous[0];
                    long cycleMatches = matched - previous[1];
                    // 只跳过剩余部分的完整循环，不足一轮的尾部继续扫描。
                    int cycles = (n1 - rounds) / cycleRounds;

                    rounds += cycles * cycleRounds;
                    matched += (long) cycles * cycleMatches;
                    accelerated = true;
                }
            }
        }

        // 累计量是单份目标词的个数，还需按每组所需份数折算。
        return (int) (matched / n2);
    }
}

type snapshot struct {
    rounds  int
    matched int64
}

func getMaxRepetitions(s1 string, n1 int, s2 string, n2 int) int {
    seen := map[int]snapshot{0: {}}
    index, rounds := 0, 0
    var matched int64
    accelerated := false

    for rounds < n1 {
        for i := 0; i < len(s1); i++ {
            if s1[i] == s2[index] {
                index++
                if index == len(s2) {
                    index = 0
                    matched++
                }
            }
        }
        rounds++

        if !accelerated {
            if previous, ok := seen[index]; ok {
                // 相同匹配下标之间的轮数差和产出差构成一个循环节。
                cycleRounds := rounds - previous.rounds
                cycleMatches := matched - previous.matched
                // 只跳过剩余部分的完整循环，不足一轮的尾部继续扫描。
                cycles := (n1 - rounds) / cycleRounds
                rounds += cycles * cycleRounds
                matched += int64(cycles) * cycleMatches
                accelerated = true
            } else {
                seen[index] = snapshot{rounds: rounds, matched: matched}
            }
        }
    }
    // 累计量是单份目标词的个数，还需按每组所需份数折算。
    return int(matched / int64(n2))
}

复杂度分析

  • 时间复杂度：$O(1+\min(n_1,\lvert s_2\rvert)\cdot\lvert s_1\rvert)$。块边界状态最多有 $\lvert s_2\rvert$ 种，发现循环前与跳过后的尾部各至多扫描这么多份 s1。
  • 空间复杂度：$O(1+\min(n_1,\lvert s_2\rvert))$，保存不同下标的快照。

关键点总结

[!green]

  • 循环状态是匹配位置，不包含不断增加的累计产出。
  • 跳跃同时增加轮数和匹配数，匹配位置保持不变。
  • 不足完整循环的尾部仍需处理。
  • 循环产出可以为零；跳跃次数按循环轮数计算，不对产出做除法。

易错点总结

[!yellow]

  • 按连续子串匹配：子序列允许跳过无关字符。
  • 循环长度直接取当前轮数：应减去前一次相同状态的轮数。
  • 只更新轮数不更新产出：跳过的匹配结果丢失。
  • 忘记除以 n2：返回的是 s2 份数。

相似题目

题目 难度 关联与区别
392. 判断子序列 简单 重复串匹配的基本步骤仍是子序列双指针，本题通过块边界状态循环跳过大量重复副本。
418. 屏幕可显示句子的数量 中等 同样反复处理固定块并检测状态周期，原题按屏幕行放词，本题按源串副本匹配目标。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/70484811
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！