[릿코드 1297] Maximum Number of Occurrences of a Substring (파이썬/python)

https://leetcode.com/problems/maximum-number-of-occurrences-of-a-substring/description/

Maximum Number of Occurrences of a Substring - LeetCode

 

start 포인터와 end 포인터를 동적으로 움직여주며 O(N) 시간 안에 가능한 모든 sub_str 을 뽑아내어 확인하는 문제였습니다.

다 풀고나서 다른 분들의 토론을 보았는데 maxSize 는 아예 고려할 필요가 없었습니다.

왜냐하면 만약 minSize 가 3이고 maxSize가 4일때 

size 가4 인 aaba 가 두번나왔다면

size가 3인 aab 는 적어도 2번은 나올겁니다(상황에따라 이상일 수 있음)

 

즉 maxSize의 경우는 minSize의 경우를 무조건 포함하고

심지어 minSize만 탐색하는것이 횟수측면에서는 더욱 더 빠른 시간 안에 답을 얻어낼 수 있습니다.

 

 

제가 푼 코드:

import collections


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        sub_str_dic = collections.defaultdict(int)

        start = 0
        end = start + minSize

        while len(s) >= end:
            if end - start > maxSize:
                start += 1
                continue
            elif end - start < minSize:
                end += 1
                continue

            sub_str = s[start:end]
            if self.check_duplicate_char(sub_str, maxLetters):
                sub_str_dic[sub_str] += 1

            if end - start == minSize:
                end += 1
            else:
                start += 1

        return max(sub_str_dic.values()) if sub_str_dic else 0

    def check_duplicate_char(self, sub_str: str, max_letters: int) -> bool:
        char_set = set(sub_str)

        if max_letters < len(char_set):
            return False

        return True

 

 

토론을 보고 수정한 코드: 훨씬빠름

import collections


class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        sub_str_dic = collections.defaultdict(int)

        start = 0
        end = start + minSize

        while len(s) >= end:
            sub_str = s[start:end]
            if self.check_duplicate_char(sub_str, maxLetters):
                sub_str_dic[sub_str] += 1
            
            # 어짜피 같은 크기만 관찰할것이므로(minSize) start와 end를 같이 1씩 움직여준다
            start += 1
            end += 1

        return max(sub_str_dic.values()) if sub_str_dic else 0

    def check_duplicate_char(self, sub_str: str, max_letters: int) -> bool:
        char_set = set(sub_str)

        if max_letters < len(char_set):
            return False

        return True