[LeetCode] 1456. Maximum Number of Vowels in a Substring of Given Length 해설 및 풀이 (Python)

LeetCode 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/description/?envType=study-plan-v2&envId=leetcode-75

 

---

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'.

 

Example 1:

Input: s = "abciiidef", k = 3
Output: 3
Explanation: The substring "iii" contains 3 vowel letters.
Example 2:

Input: s = "aeiou", k = 2
Output: 2
Explanation: Any substring of length 2 contains 2 vowels.
Example 3:

Input: s = "leetcode", k = 3
Output: 2
Explanation: "lee", "eet" and "ode" contain 2 vowels.
 

Constraints:

1 <= s.length <= 105
s consists of lowercase English letters.
1 <= k <= s.length

 

한글 번역

주어진 문자열 s와 정수 k가 있을 때, 길이가 k인 모든 부분 문자열 중에서 **모음(a, e, i, o, u)**의 개수가 가장 많은 값을 반환하세요.

예시:

예시 1:

• 입력: s = "abciiidef", k = 3
• 출력: 3
• 설명: 부분 문자열 "iii"에는 3개의 모음이 포함되어 있습니다.

예시 2:

• 입력: s = "aeiou", k = 2
• 출력: 2
• 설명: 길이가 2인 모든 부분 문자열에는 항상 2개의 모음이 포함됩니다.

예시 3:

• 입력: s = "leetcode", k = 3
• 출력: 2
• 설명: "lee", "eet", "ode" 등의 부분 문자열에는 각각 2개의 모음이 포함되어 있습니다.

---

제약 사항:

• 1 <= s.length <= 10^5
• s는 영어 소문자로만 이루어져 있습니다.
• 1 <= k <= s.length

 

---

문제 유형

문자열

슬라이딩 윈도우

 

풀이 방법 도출

 

이 문제는 슬라이딩 윈도우를 사용하여 해결합니다.

 

1. 윈도우의 크기를 k로 유지하면서, 매번 해당 구간 내의 모음 수를 계산합니다.
2. 매번 새 문자가 들어오면 모음인지 확인해서 current_count를 증가시킵니다.
3. 윈도우의 왼쪽 문자가 제거되면 그것이 모음인지 확인해서 current_count를 감소시킵니다.
4. 현재 구간에서의 모음 수(current_count)를 최대값(max_count)과 비교하여 갱신합니다.

 

 

시간 복잡도

• O(N)

---

핵심 코드 삽입 및 설명

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowels = 'aeiou'  # 모음 목록
        max_count = 0     # 최대 모음 수
        current_count = 0 # 현재 윈도우 내 모음 수
        left = 0          # 윈도우의 시작 인덱스

        for right in range(len(s)):
            # 오른쪽 문자 추가
            if s[right] in vowels:
                current_count += 1

            # 윈도우 크기가 k 초과할 경우 왼쪽 문자 제거
            if right - left + 1 > k:
                if s[left] in vowels:
                    current_count -= 1
                left += 1  # 왼쪽 포인터 이동

            # 최대 모음 수 갱신
            max_count = max(max_count, current_count)

        return max_count