[Leetcode] 1456 Maximum Number of Vowels in a Substring of Given Length (Python)

문제

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

설명

Given a string s and an integer k, return the maximum number of vowel letters in any substring of s with length k.

Vowel letters in English are 'a', 'e', 'i', 'o', and 'u'.

풀이 계획

가장 많은 모음이 포함된 k의 길이만큼의 문자열에서의 모음의 갯수를 구하는 문제이다.

초기 풀이 (8384ms, 18.22MB)

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowels="aeiou"
        maxnum = 0
        start = 0
        end = k
        for i in range(len(s)-k):
            total = sum(s[start:end].count(vowel) for vowel in vowels)
            maxnum = total if total > maxnum else maxnum
            start+=1
            end+=1

        return maxnum

문제점 및 해결 방안

일단 반복문의 범위가 len(s)-k까지여서 문자열의 마지막보다 하나 앞까지만 검사하고 끝나는 것 때문에 통과가 되지 않았다. 그리고 start와 end를 하나씩 밀 때마다 모음이 몇개인지 검사하는 것이 비효율적으로 느껴져서 보기 싫었다.

고친 풀이 (51ms, 18.14MB)

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowels="aeiou"
        start = 0
        end = k
        v_max = v_num = sum(s[start:end].count(vowel) for vowel in vowels)
        start, end = start + 1, end + 1
        for _ in range(start, len(s)-k+1):
            if s[start-1] in vowels:
                v_num-=1
            if s[end-1] in vowels:
                v_num+=1
            v_max = v_num if v_num > v_max else v_max
            start, end = start + 1, end + 1
        return v_max

고친 풀이2 (69ms, 17.90MB)

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowels = "aeiou"
        v_num = sum(s[i] in vowels for i in range(k))
        v_max = v_num
        for i in range(k, len(s)):
            if s[i - k] in vowels:
                v_num -= 1
            if s[i] in vowels:
                v_num += 1
            v_max = max(v_max, v_num)
        return v_max

시간복잡도 : O(N)

공간복잡도 : O(1)