LeetCode-1297. Maximum Number of Occurrences of a Substring

LeetCode-1297. Maximum Number of Occurrences of a Substring

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 = 4Output: 2Explanation: 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 = 3Output: 2Explanation: Substring "aaa" occur 2 times in the string. It can overlap.

Example 3:

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

Example 4:

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

Constraints:

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

题解：

完全可以不需要maxSize，因为minSize肯定包含了maxSize的子串。

字典树做法：

class Solution {private: struct TrieTree { TrieTree* child[26]; int count; unordered_set letters; TrieTree() { for (int i = 0; i < 26; i++) { child[i] = NULL; } count = 0; } }; void insert(TrieTree *root, string word) { TrieTree *t = root; unordered_set letters; for (int i = 0; i < word.size(); i++) { letters.insert(word[i]); if (t->child[word[i]- 'a'] == NULL) { t->child[word[i] - 'a'] = new TrieTree(); } t = t->child[word[i] - 'a']; t->letters = letters; } t->letters = letters; t->count++; } void visit(TrieTree *root, int &res, int maxLetters) { if (root != NULL) { if (root->letters.size() <= maxLetters) { res = max(res, root->count); } for (int i = 0; i < 26; i++) { if (root->child[i] != NULL) { visit(root->child[i], res, maxLetters); } } } }public: int maxFreq(string s, int maxLetters, int minSize, int maxSize) { TrieTree *root = new TrieTree(); for (int i = 0; i <= s.length() - minSize; i++) { string sub = s.substr(i, minSize); insert(root, sub); } int res = 0; visit(root, res, maxLetters); return res; }};

map做法：

class Solution {public: int calLetters(string s) { unordered_set st; for (int i = 0; i < s.length(); i++) { st.insert(s[i]); } return st.size(); } int maxFreq(string s, int maxLetters, int minSize, int maxSize) { unordered_map m; for (int i = 0; i < s.length(); i++) { if (i + minSize <= s.length()) { string sub = s.substr(i, minSize); m[sub]++; } } int res = 0; for (auto it = m.begin(); it != m.end(); it++) { if (calLetters(it->first) <= maxLetters) { res = max(res, it->second); } } return res; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。