1297

1297. Maximum Number of Occurrences of a Substring (Medium)

Given a string s, return the maximum number of ocurrences 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 ocurrences 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.

Example 3:

Input: s = "aabcabcab", maxLetters = 2, minSize = 2, maxSize = 3
Output: 3

Example 4:

Input: s = "abcde", maxLetters = 2, minSize = 3, maxSize = 3
Output: 0

 

Constraints:

• 1 <= s.length <= 10^5
• 1 <= maxLetters <= 26
• 1 <= minSize <= maxSize <= min(26, s.length)
• s only contains lowercase English letters.

Companies:
Twitter

Related Topics:
String, Bit Manipulation

Solution 1. Rabin Karp

// OJ: https://leetcode.com/problems/maximum-number-of-occurrences-of-a-substring/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
        unsigned h = 0, p = 1, d = 16777619, ans = 0;
        unordered_map<unsigned, unsigned> cnt, m;
        for (int i = 0; i < s.size(); ++i) {
            h = h * d + s[i] - 'a';
            m[s[i]]++;
            if (i < minSize) {
                p *= d;
            }
            if (i >= minSize) {
                h -= p * (s[i - minSize] - 'a');
                if (--m[s[i - minSize]] == 0) m.erase(s[i - minSize]);
            }
            if (i >= minSize - 1 && m.size() <= maxLetters) {
                ans = max(ans, ++cnt[h]);
            }
        }
        return ans;
    }
};