1297. Maximum Number of Occurrences of a Substring

Description

Given a string s, return the maximum number of occurrences of any substring under the following rules:

The number of unique characters in the substring must be less than or equal to maxLetters.
The substring size must be between minSize and maxSize inclusive.

Example 1:

Input: s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4
Output: 2
Explanation: Substring "aab" has 2 occurrences in the original string.
It satisfies the conditions, 2 unique letters and size 3 (between minSize and maxSize).

Example 2:

Input: s = "aaaa", maxLetters = 1, minSize = 3, maxSize = 3
Output: 2
Explanation: Substring "aaa" occur 2 times in the string. It can overlap.

Constraints:

1 <= s.length <= 10⁵
1 <= maxLetters <= 26
1 <= minSize <= maxSize <= min(26, s.length)
s consists of only lowercase English letters.

Solutions

Solution 1: Hash Table + Enumeration

According to the problem description, if a long string meets the condition, then its substring of length \(\textit{minSize}\) must also meet the condition. Therefore, we only need to enumerate all substrings of length \(\textit{minSize}\) in \(s\), then use a hash table to record the occurrence frequency of all substrings, and find the maximum frequency as the answer.

The time complexity is \(O(n \times m)\), and the space complexity is \(O(n \times m)\). Here, \(n\) and \(m\) are the lengths of the string \(s\) and \(\textit{minSize}\), respectively. In this problem, \(m\) does not exceed \(26\).

Python3JavaC++GoTypeScriptRust

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

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.merge(t, 1, Integer::sum);
                ans = Math.max(ans, cnt.get(t));
            }
        }
        return ans;
    }
}

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;
    }
};

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
}

function maxFreq(s: string, maxLetters: number, minSize: number, maxSize: number): number {
    const cnt = new Map<string, number>();
    let ans = 0;
    for (let i = 0; i < s.length - minSize + 1; ++i) {
        const t = s.slice(i, i + minSize);
        const ss = new Set(t.split(''));
        if (ss.size <= maxLetters) {
            cnt.set(t, (cnt.get(t) || 0) + 1);
            ans = Math.max(ans, cnt.get(t)!);
        }
    }
    return ans;
}

use std::collections::{HashMap, HashSet};

impl Solution {
    pub fn max_freq(s: String, max_letters: i32, min_size: i32, _max_size: i32) -> i32 {
        let n = s.len();
        let m = min_size as usize;
        let max_letters = max_letters as usize;
        let bytes = s.as_bytes();
        let mut cnt: HashMap<&[u8], i32> = HashMap::new();
        let mut ans = 0;

        for i in 0..=n - m {
            let t = &bytes[i..i + m];

            let mut set = HashSet::new();
            for &c in t {
                set.insert(c);
                if set.len() > max_letters {
                    break;
                }
            }
            if set.len() <= max_letters {
                let v = cnt.entry(t).or_insert(0);
                *v += 1;
                ans = ans.max(*v);
            }
        }

        ans
    }
}

Solution 2: Sliding Window + String Hashing

We can use a sliding window to maintain the number of distinct letters in the current substring, while using string hashing to efficiently calculate the hash value of substrings, thereby avoiding using strings as hash table keys and improving performance.

Specifically, we define a \(\textit{Hashing}\) class to preprocess the prefix hash values and power values of the string \(s\), so that we can calculate the hash value of any substring in \(O(1)\) time.

Then, we use a sliding window to traverse the string \(s\), maintaining the number of distinct letters in the current window. When the window size reaches \(\textit{minSize}\), we calculate the hash value of the current substring and update its occurrence count. Next, we slide the window one position to the right and update the letter frequencies and the count of distinct letters.

The time complexity is \(O(n)\) and the space complexity is \(O(n)\), where \(n\) is the length of the string \(s\).