LeetCode 솔루션

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

Jack 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.05.12 21:35

14,462 조회
3 댓글
0 추천
0 비추천
목록 게시글 쓰기

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.

#leetcode, #문제풀이, #시즌3, #amazon, #zoom, #hash table, #string, #sliding window

링크

https://leetcode.com/problems/maximum-number-of-occurrences-of-a-substring/ 4505 회 연결

익명
작성일 2022.05.12 22:04

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;
    }
};

익명
작성일 2022.05.12 23:33

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;
    }
};

익명
작성일 2022.05.13 01:00

문제 풀이 감사합니다.