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++GoTypeScript

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.put(t, cnt.getOrDefault(t, 0) + 1);
                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;
}

1297. Maximum Number of Occurrences of a Substring

Description

Solutions

Solution 1: Hash Table + Enumeration

Comments