LeetCode 솔루션 분류
[Interview] 1297. Maximum Number of Occurrences of a Substring
본문
1297. Maximum Number of Occurrences of a Substring
Medium
618298Add to ListShareGiven 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
minSizeandmaxSizeinclusive.
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.
Constraints:
1 <= s.length <= 1051 <= maxLetters <= 261 <= minSize <= maxSize <= min(26, s.length)sconsists of only lowercase English letters.
관련자료
-
링크
댓글 3
mingki님의 댓글
- 익명
- 작성일
5/12 미팅 문제풀이
class Solution {
public:
int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
if (s.empty() || minSize > s.size() || maxSize == 0 || maxLetters == 0 || minSize > maxSize)
return 0;
map<string, int> m;
int n = s.size();
set<char> unique;
for (int i = 0; i < n - minSize + 1; ++i) {
unique.clear();
string substr = "";
for (int j = i; j < n; ++j) {
unique.insert(s[j]);
if (unique.size() > maxLetters) {
break;
}
substr += s[j];
if (substr.size() >= minSize) {
m[substr] += 1;
break;
}
}
}
int result = 0;
for (auto &item : m) {
result = max(result, item.second);
}
return result;
}
};austin님의 댓글
- 익명
- 작성일
Runtime: 39 ms, faster than 97.62% of C++ online submissions for Maximum Number of Occurrences of a Substring.
Memory Usage: 13.1 MB, less than 91.43% of C++ online submissions for Maximum Number of Occurrences of a Substring.
Memory Usage: 13.1 MB, less than 91.43% of C++ online submissions for Maximum Number of Occurrences of a Substring.
class Solution {
public:
int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
int ret = 0;
for(auto [unique, to, m, occur] = tuple(0, 0, unordered_map<string, int>(), vector<int>(26));
to < s.size(); ++to) {
if (++occur[s[to]-'a'] == 1) ++unique;
if (to >= minSize && !--occur[s[to-minSize]-'a']) --unique;
if (to+1 >= minSize && unique <= maxLetters) ret = max(ret, ++m[s.substr(to+1-minSize, minSize)]);
}
return ret;
}
};
