Hard

题目描述

我们定义 str = [s, n] 表示 str 由字符串 s 连接 n 次构成。

  • 例如，str == ["abc", 3] == "abcabcabc"。

我们定义，如果从字符串 s2 中删除某些字符能够得到字符串 s1，那么字符串 s1 可以从字符串 s2 获得。

  • 例如，根据定义，s1 = "abc" 可以从 s2 = "abdbec" 获得，只需要删除加粗且用下划线标出的字符。

现在给你两个字符串 s1 和 s2 和两个整数 n1 和 n2。由此构造得到两个字符串，其中 str1 = [s1, n1]、str2 = [s2, n2]。

请你找出一个最大整数 m，使得 str = [str2, m] 可以从 str1 获得。

示例 1：

输入：s1 = "acb", n1 = 4, s2 = "ab", n2 = 2
输出：2

示例 2：

输入：s1 = "acb", n1 = 1, s2 = "acb", n2 = 1
输出：1

提示：

  • 1 <= s1.length, s2.length <= 100
  • s1 和 s2 由小写英文字母组成
  • 1 <= n1, n2 <= 10^6

解题思路

这道题的核心是计算 [s1, n1] 中最多能包含多少个 [s2, n2]。

思路分析

首先需要理解题意：我们有字符串 s1 重复 n1 次形成的长字符串，要在其中找到最多能形成多少个由字符串 s2 重复 n2 次组成的子序列。

方法一：暴力模拟 直接模拟匹配过程，遍历 [s1, n1]，尝试匹配 s2，记录能匹配多少个完整的 s2。但这种方法在 n1 很大时会超时。

方法二：循环检测优化（推荐） 由于 s1 和 s2 的长度都不超过 100，当我们遍历多个 s1 时，必然会出现循环模式。我们可以检测这种循环：

  1. 记录每次遍历完一个 s1 后，在 s2 中的位置
  2. 当出现相同位置时，说明找到了循环
  3. 利用循环的性质快速计算结果

具体实现：

  • 用数组记录每次遍历完 s1 后的状态（在 s2 中的位置和已匹配的 s2 个数）
  • 检测到循环后，计算循环内能匹配多少个 s2
  • 最后计算总共能形成多少个 [s2, n2]

时间复杂度优化到 O(|s1| × |s2|)，空间复杂度 O(|s2|)。

代码实现

class Solution {
public:
    int getMaxRepetitions(string s1, int n1, string s2, int n2) {
        if (n1 == 0) return 0;
        
        vector<int> s1_counts(s2.size() + 1, 0);  // s1_counts[i] 表示匹配到s2[i]位置时，用了多少个s1
        vector<int> s2_counts(s2.size() + 1, 0);  // s2_counts[i] 表示匹配到s2[i]位置时，匹配了多少个完整的s2
        
        int s1_count = 0, s2_count = 0;
        int s2_index = 0;
        
        while (s1_count < n1) {
            s1_count++;
            for (char c : s1) {
                if (c == s2[s2_index]) {
                    s2_index++;
                    if (s2_index == s2.size()) {
                        s2_count++;
                        s2_index = 0;
                    }
                }
            }
            
            // 检测循环
            if (s1_counts[s2_index] > 0) {
                // 找到循环
                int prev_s1_count = s1_counts[s2_index];
                int prev_s2_count = s2_counts[s2_index];
                
                int cycle_s1 = s1_count - prev_s1_count;
                int cycle_s2 = s2_count - prev_s2_count;
                
                int remaining_s1 = n1 - s1_count;
                int cycle_times = remaining_s1 / cycle_s1;
                
                s2_count += cycle_times * cycle_s2;
                s1_count += cycle_times * cycle_s1;
            }
            
            s1_counts[s2_index] = s1_count;
            s2_counts[s2_index] = s2_count;
        }
        
        return s2_count / n2;
    }
};

class Solution:
    def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:
        if n1 == 0:
            return 0
        
        s1_counts = [0] * (len(s2) + 1)  # s1_counts[i] 表示匹配到s2[i]位置时，用了多少个s1
        s2_counts = [0] * (len(s2) + 1)  # s2_counts[i] 表示匹配到s2[i]位置时，匹配了多少个完整的s2
        
        s1_count = s2_count = s2_index = 0
        
        while s1_count < n1:
            s1_count += 1
            for c in s1:
                if c == s2[s2_index]:
                    s2_index += 1
                    if s2_index == len(s2):
                        s2_count += 1
                        s2_index = 0
            
            # 检测循环
            if s1_counts[s2_index] > 0:
                # 找到循环
                prev_s1_count = s1_counts[s2_index]
                prev_s2_count = s2_counts[s2_index]
                
                cycle_s1 = s1_count - prev_s1_count
                cycle_s2 = s2_count - prev_s2_count
                
                remaining_s1 = n1 - s1_count
                cycle_times = remaining_s1 // cycle_s1
                
                s2_count += cycle_times * cycle_s2
                s1_count += cycle_times * cycle_s1
            
            s1_counts[s2_index] = s1_count
            s2_counts[s2_index] = s2_count
        
        return s2_count // n2

public class Solution {
    public int GetMaxRepetitions(string s1, int n1, string s2, int n2) {
        if (n1 == 0) return 0;
        
        int[] s1Counts = new int[s2.Length + 1];  // s1Counts[i] 表示匹配到s2[i]位置时，用了多少个s1
        int[] s2Counts = new int[s2.Length + 1];  // s2Counts[i] 表示匹配到s2[i]位置时，匹配了多少个完整的s2
        
        int s1Count = 0, s2Count = 0, s2Index = 0;
        
        while (s1Count < n1) {
            s1Count++;
            foreach (char c in s1) {
                if (c == s2[s2Index]) {
                    s2Index++;
                    if (s2Index == s2.Length) {
                        s2Count++;
                        s2Index = 0;
                    }
                }
            }
            
            // 检测循环
            if (s1Counts[s2Index] > 0) {
                // 找到循环
                int prevS1Count = s1Counts[s2Index];
                int prevS2Count = s2Counts[s2Index];
                
                int cycleS1 = s1Count - prevS1Count;
                int cycleS2 = s2Count - prevS2Count;
                
                int remainingS1 = n1 - s1Count;
                int cycleTimes = remainingS1 / cycleS1;
                
                s2Count += cycleTimes * cycleS2;
                s1Count += cycleTimes * cycleS1;
            }
            
            s1Counts[s2Index] = s1Count;
            s2Counts[s2Index] = s2Count;
        }
        
        return s2Count / n2;
    }
}

var getMaxRepetitions = function(s1, n1, s2, n2) {
    if (n1 === 0) return 0;
    
    let s1Count = 0, s2Count = 0, s2Idx = 0;
    let memo = new Map();
    
    while (s1Count < n1) {
        for (let i = 0; i < s1.length; i++) {
            if (s1[i] === s2[s2Idx]) {
                s2Idx++;
                if (s2Idx === s2.length) {
                    s2Count++;
                    s2Idx = 0;
                }
            }
        }
        s1Count++;
        
        if (memo.has(s2Idx)) {
            let [prevS1Count, prevS2Count] = memo.get(s2Idx);
            let cycleS1 = s1Count - prevS1Count;
            let cycleS2 = s2Count - prevS2Count;
            
            let remainingS1 = n1 - s1Count;
            let completeCycles = Math.floor(remainingS1 / cycleS1);
            s2Count += completeCycles * cycleS2;
            s1Count += completeCycles * cycleS1;
        } else {
            memo.set(s2Idx, [s1Count, s2Count]);
        }
    }
    
    return Math.floor(s2Count / n2);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(|s1| × |s2|)，最坏情况下需要遍历 |s2| 个不同状态，每个状态需要遍历一次 s1
空间复杂度O(|s2|)，需要存储每个 s2 位置对应的状态信息