[leetcode] 슬라이딩 윈도우의 장점: 매번 전체 윈도우를 다시 계산하지 않고 양 끝 변화만 업데이트

슬라이딩 윈도우의 장점을 살리지 못한 코드:

중첩 for문(k는 작은 상수 값)

O(n*k)

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowels = set('aeiou')
        max_count = 0
        
        # 올바른 범위: len(s)-k+1
        for i in range(len(s)-k+1):
            count = 0
            for j in range(i, i+k):
                if s[j] in vowels:
                    count += 1
            max_count = max(max_count, count)
        
        return max_count

슬라이딩 윈도우의 장점을 살린 코드:

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowels = set('aeiou')
        
        # 첫 번째 윈도우의 모음 개수 계산
        count = 0
        for i in range(k):
            if s[i] in vowels:
                count += 1
        
        max_count = count
        
        # 슬라이딩 윈도우로 나머지 확인
        for i in range(k, len(s)):
            # 왼쪽 문자 제거
            if s[i-k] in vowels:
                count -= 1
            # 오른쪽 문자 추가
            if s[i] in vowels:
                count += 1
            
            max_count = max(max_count, count)
        
        return max_count