跳转至

1297. 子串的最大出现次数

题目描述

给你一个字符串 s ，请你返回满足以下条件且出现次数最大的 任意 子串的出现次数：

  • 子串中不同字母的数目必须小于等于 maxLetters 。
  • 子串的长度必须大于等于 minSize 且小于等于 maxSize 。

 

示例 1：

输入：s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4
输出：2
解释：子串 "aab" 在原字符串中出现了 2 次。
它满足所有的要求：2 个不同的字母，长度为 3 （在 minSize 和 maxSize 范围内）。

示例 2：

输入：s = "aaaa", maxLetters = 1, minSize = 3, maxSize = 3
输出：2
解释：子串 "aaa" 在原字符串中出现了 2 次，且它们有重叠部分。

示例 3：

输入：s = "aabcabcab", maxLetters = 2, minSize = 2, maxSize = 3
输出：3

示例 4：

输入：s = "abcde", maxLetters = 2, minSize = 3, maxSize = 3
输出：0

 

提示：

  • 1 <= s.length <= 10^5
  • 1 <= maxLetters <= 26
  • 1 <= minSize <= maxSize <= min(26, s.length)
  • s 只包含小写英文字母。

解法

方法一：哈希表 + 枚举

根据题目描述，如果一个长串满足条件，那么这个长串的子串（长度至少为 minSize）也一定满足条件。因此，我们只需要枚举 $s$ 中所有长度为 minSize 的子串，然后利用哈希表记录所有子串的出现次数，找出最大的次数作为答案即可。

时间复杂度 $O(n \times m)$，空间复杂度 $O(n \times m)$。其中 $n$ 和 $m$ 分别为字符串 $s$ 的长度以及 minSize 的大小。本题中 $m$ 不超过 $26$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        ans = 0
        cnt = Counter()
        for i in range(len(s) - minSize + 1):
            t = s[i : i + minSize]
            ss = set(t)
            if len(ss) <= maxLetters:
                cnt[t] += 1
                ans = max(ans, cnt[t])
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
        int ans = 0;
        Map<String, Integer> cnt = new HashMap<>();
        for (int i = 0; i < s.length() - minSize + 1; ++i) {
            String t = s.substring(i, i + minSize);
            Set<Character> ss = new HashSet<>();
            for (int j = 0; j < minSize; ++j) {
                ss.add(t.charAt(j));
            }
            if (ss.size() <= maxLetters) {
                cnt.put(t, cnt.getOrDefault(t, 0) + 1);
                ans = Math.max(ans, cnt.get(t));
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
        int ans = 0;
        unordered_map<string, int> cnt;
        for (int i = 0; i < s.size() - minSize + 1; ++i) {
            string t = s.substr(i, minSize);
            unordered_set<char> ss(t.begin(), t.end());
            if (ss.size() <= maxLetters) {
                ans = max(ans, ++cnt[t]);
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func maxFreq(s string, maxLetters int, minSize int, maxSize int) (ans int) {
    cnt := map[string]int{}
    for i := 0; i < len(s)-minSize+1; i++ {
        t := s[i : i+minSize]
        ss := map[rune]bool{}
        for _, c := range t {
            ss[c] = true
        }
        if len(ss) <= maxLetters {
            cnt[t]++
            if ans < cnt[t] {
                ans = cnt[t]
            }
        }
    }
    return
}

评论