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

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

작성자 정보

  • Jack 작성
  • 작성일

컨텐츠 정보

본문

1297. Maximum Number of Occurrences of a Substring
Medium
618298Add to ListShare

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 페이지
게시글 쓰기
번호
제목
이름

최근글


새댓글


Stats


  • 현재 접속자 85 명
  • 오늘 방문자 140 명
  • 어제 방문자 938 명
  • 최대 방문자 1,221 명
  • 전체 회원수 216 명
알림 0