엔지니어 게시판
LeetCode 솔루션 분류

# [Interview] 1297. Maximum Number of Occurrences of a Substring

• Jack 작성
• 작성일

• 222 조회
• 3 댓글

### 본문

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.
```

Constraints:

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

댓글 3

## mingki님의 댓글

• 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님의 댓글

• 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.
``````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;
}
};``````

## Jack님의 댓글의 댓글

• Jack
• 작성일
문제 풀이 감사합니다.
전체 85 / 1 페이지

• 등록일 05.21
• 등록일 05.21
• 등록일 05.21
• 등록일 05.21
• 등록일 05.21
• 등록일 05.21
• 등록일 05.21
• 등록일 05.21
• 등록일 05.21

### 새댓글

• 등록자 뚝배기 등록일 05.21
• 등록자 coderoncruise 등록일 05.21
• 등록자 coderoncruise 등록일 05.21
• 등록자 Connie 등록일 05.21
• 등록자 JakeMinSVK 등록일 05.21
• 등록자 JakeMinSVK 등록일 05.21
• 등록자 Connie 등록일 05.20
• 등록자 Jack 등록일 05.20
• 등록자 Connie 등록일 05.19
• 등록자 Connie 등록일 05.19

### Stats

• 현재 접속자 82 명
• 오늘 방문자 87 명
• 어제 방문자 938 명
• 최대 방문자 1,221 명
• 전체 회원수 216 명