【LeetCode】Day172-最大重复子字符串

题目

1668. 最大重复子字符串【简单】

题解

暴力解法可以过，这大概是这道题简单的唯一原因了吧…

暴力法

直接挨个试，找word的连续最大重复次数

class Solution {
    public int maxRepeating(String sequence, String word) {
        int n=sequence.length(),m=word.length(),max=0;
        for(int i=0;i<=n-m;i++){
            int res=0,j=i;
            while(j+m<=n&&sequence.substring(j,j+m).equals(word)){
                res++;
                j+=m;
            }
            max=Math.max(max,res);
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

时间复杂度：$O(n^{2}m)$

空间复杂度：$O(1)$

枚举+动态规划

序列dp入门题

将sequence的每一个位置作为结束位置，判断前面的m个字符是否恰好是字符串word。

1. 状态定义：dp[i] 表示word在第 i 个位置最后一次出现时的最大重复值。
2. 状态转移方程：设word长度为m，
   如果 i>=m 且 sequence[i-m…i]==word ：dp[i]=dp[ i-m ]+1（重复度+1）
3. 初始条件：
   dp[i]=0
4. 返回值：max(dp[i])

class Solution {
    public int maxRepeating(String sequence, String word) {
        int n=sequence.length(),m=word.length(),max=0;
        int[] dp=new int[n+1];
        for(int i=m;i<=n;i++){
            if(sequence.substring(i-m,i).equals(word))
                dp[i]=dp[i-m]+1;
            max=Math.max(max,dp[i]);
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

时间复杂度：$O(n\ast m)$

空间复杂度：$O(n)$