1456. Maximum Number of Vowels in a Substring of Given Length

https://leetcode.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length/

Maximum Number of Vowels in a Substring of Given Length - LeetCode

문자열 s와 정수 k가 주어졌을 때, 길이가 k인 s의 부분 문자열에서 모음 글자의 최대 개수를 반환한다.
영어의 모음 문자는 'a', 'e', 'i', 'o', 'u'다.

 

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowels = "aeiou"
        max_cnt, cnt = 0, 0

        for word in s[:k]: # O(k)
            if word in vowels: # O(v) v는 vowels 문자열 길이
                cnt += 1

        max_cnt = cnt

        for i in range(k, len(s)): # O(n - k)
            if s[i] in vowels: # O(v)
                cnt += 1
            if s[i - k] in vowels: # O(v)
                cnt -= 1
            max_cnt = max(cnt, max_cnt) # O(1)
        
        return max_cnt

 

슬라이싱 윈도우 방식으로 문제를 풀이했다.

맨 처음 k의 길이만큼 부분 문자열을 만들고 모음 글자의 개수를 계산했다.

이후 포인터를 한 칸씩 이동하며 모음 글자의 여부에 따라 개수를 증감시켰다. 그리고 max_cnt를 갱신했다.

 

이렇게 모든 문자열을 O(n)의 시간복잡도로 순회하면서 길이가 k인 부분 문자열 중 모음 글자의 최대 개수를 구할 수 있다.

공간복잡도는 vowels 문자열의 길이만큼 할당하므로 O(v)이다.