LeetCode 466. 统计重复个数

Categories:

题目描述
思路分析
1. 解法一：循环节检测（推荐）
相似题目

题目描述

✅ 466. 统计重复个数

思路分析

解法一：循环节检测（推荐）

核心思路：

将 s1 重复 n1 次，从中删去 s2 的字符，统计能匹配多少个完整 s2；最终结果为匹配总数除以 n2

关键优化：遍历 s1 时记录每轮结束时 s2 的索引位置，若某个索引位置出现重复，则找到了循环节

找到循环节后，可以直接计算大段重复的贡献，再单独处理首尾不完整的部分，从而避免 O(n1 × s1 ) 的暴力枚举

循环节长度最多为 s2 ，因此只需遍历至多 s2 + 1 轮 s1 即可找到循环

复杂度分析：

时间复杂度：O( s1 × s2 )，其中循环节检测最多执行 s2 轮，每轮遍历 s1

空间复杂度：O( s2 )，存储每个 s2 索引位置对应的状态

class Solution {

  public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
    int len1 = s1.length();
    int len2 = s2.length();

    // indexMap[i] 记录：s2 索引为 i 时，完整遍历了几轮 s1 以及匹配了多少个 s2
    int[] s1Count = new int[len2 + 1];
    int[] s2Count = new int[len2 + 1];
    int s2Index = 0;
    int s2Total = 0;

    for (int i = 0; i < n1; i++) {
      for (int j = 0; j < len1; j++) {
        if (s1.charAt(j) == s2.charAt(s2Index)) {
          s2Index++;
          if (s2Index == len2) {
            s2Index = 0;
            s2Total++;
          }
        }
      }

      // 记录第 i 轮结束时的状态
      s1Count[i] = i;
      s2Count[i] = s2Total;

      // 检测循环节：s2Index 已经出现过
      for (int k = 0; k < i; k++) {
        if (s2Index == k % len2) {
          // 找到循环节，计算前缀 + 完整循环 + 后缀
          int prefixS2 = s2Count[k];
          int cycleS2 = s2Total - prefixS2;
          int cycleLen = i - k;
          int remainRounds = (n1 - k - 1) % cycleLen;
          int totalS2 = prefixS2 + cycleS2 * ((n1 - k - 1) / cycleLen) + (s2Count[k + remainRounds] - prefixS2);
          return totalS2 / n2;
        }
      }
    }

    return s2Total / n2;
  }
}

func getMaxRepetitions(s1 string, n1 int, s2 string, n2 int) int {
    len1 := len(s1)
    len2 := len(s2)

    // 记录每轮 s1 结束时 s2 的匹配总数
    s2CountPerRound := make([]int, n1)
    s2IndexPerRound := make([]int, n1)

    s2Index := 0
    s2Total := 0

    for i := 0; i < n1; i++ {
        for j := 0; j < len1; j++ {
            if s1[j] == s2[s2Index] {
                s2Index++
                if s2Index == len2 {
                    s2Index = 0
                    s2Total++
                }
            }
        }

        s2CountPerRound[i] = s2Total
        s2IndexPerRound[i] = s2Index

        // 检测循环节
        for k := 0; k < i; k++ {
            if s2IndexPerRound[k] == s2Index {
                prefixS2 := s2CountPerRound[k]
                cycleS2 := s2Total - prefixS2
                cycleLen := i - k
                remainRounds := (n1 - k - 1) % cycleLen
                totalS2 := prefixS2 + cycleS2*((n1-k-1)/cycleLen) + (s2CountPerRound[k+remainRounds] - prefixS2)
                return totalS2 / n2
            }
        }
    }

    return s2Total / n2
}

相似题目

题目	难度	考察点
28. 找出字符串中第一个匹配项的下标	简单	字符串匹配
459. 重复的子字符串	简单	字符串、KMP
686. 重复叠加字符串匹配	中等	字符串匹配
1566. 重复至少 K 次且长度为 M 的模式	简单	字符串、枚举
1668. 最大重复子字符串	简单	字符串、动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/70484811