[LeetCode] 1456. Maximum Number of Vowels in a Substring of Given Length

🔗 Problem Link

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

---

❔Thinking

• 문자열 s와 정수 k가 주어질 때, k개의 문자를 가지는 s의 부분 문자열 가운데에서 모음(a,e,i,o,u)이 최대 몇 개인지 반환한다.
  • s = 'abciiidef', k = 3 인 경우 output은 3이다. (부분 문자열 'iii')
  • s = 'aeiou', k = 2 인 경우 output은 2이다 (어떤 부분 문자열이라도 2) 

---

💻Solution

1. two-pointer를 활용한 풀이

def maxVowels(self, s: str, k: int) -> int:
    left = 0
    max_vowel_sub = 0
    now_vowel_sub = 0
    for right in range(len(s)):
        if s[right] in {'a','e','i','o','u'}:
            now_vowel_sub += 1
        if (right-left+1) == k:
            max_vowel_sub = max(max_vowel_sub, now_vowel_sub)
            if s[left] in {'a','e','i','o','u'}:
                now_vowel_sub -= 1
            left += 1
    return max_vowel_sub

 

2. queue를 활용한 풀이

from collections import deque
def maxVowels(self, s: str, k: int) -> int:
    window = deque([])
    max_vowel_sub = 0
    now_vowel_sub = 0
    for char in s:
        window.append(char)
        if char in {'a','e','i','o','u'}:
            now_vowel_sub += 1
        if len(window) == k:
            max_vowel_sub = max(max_vowel_sub, now_vowel_sub)
            tmp = window.popleft()
            if tmp in {'a','e','i','o','u'}:
                now_vowel_sub -= 1
    return max_vowel_sub

---

🗝️keypoint

1. 만약 window에 담긴 모음을 확인한 후 window를 업데이트 할 경우, 'abcdefiii'와 같이 마지막 'iii'는 확인하지 못한다.
2. 모음을 확인하는 in 부분에서, 훨씬 더 많은 글자와 비교가 이루어져야 한다면 list 보다 set, dict이 더 효율적이다.